CSES - KILO 2017 2/5

Submission details
Task:	Evacuation
Sender:	blitzset
Submission time:	2017-09-12 18:59:28 +0300
Language:	C++
Status:	READY
Result:	OUTPUT LIMIT EXCEEDED

Test results
test	verdict	time
#1	OUTPUT LIMIT EXCEEDED	0.00 s	details
#2	OUTPUT LIMIT EXCEEDED	0.00 s	details
#3	OUTPUT LIMIT EXCEEDED	0.00 s	details
#4	OUTPUT LIMIT EXCEEDED	0.00 s	details
#5	OUTPUT LIMIT EXCEEDED	0.00 s	details
#6	OUTPUT LIMIT EXCEEDED	0.00 s	details
#7	OUTPUT LIMIT EXCEEDED	0.00 s	details
#8	WRONG ANSWER	0.06 s	details
#9	OUTPUT LIMIT EXCEEDED	0.00 s	details
#10	OUTPUT LIMIT EXCEEDED	0.00 s	details
#11	OUTPUT LIMIT EXCEEDED	0.00 s	details
#12	OUTPUT LIMIT EXCEEDED	0.00 s	details
#13	OUTPUT LIMIT EXCEEDED	0.00 s	details
#14	OUTPUT LIMIT EXCEEDED	0.00 s	details
#15	OUTPUT LIMIT EXCEEDED	0.00 s	details
#16	OUTPUT LIMIT EXCEEDED	0.00 s	details
#17	OUTPUT LIMIT EXCEEDED	0.00 s	details
#18	OUTPUT LIMIT EXCEEDED	0.00 s	details
#19	OUTPUT LIMIT EXCEEDED	0.00 s	details
#20	OUTPUT LIMIT EXCEEDED	0.00 s	details
#21	OUTPUT LIMIT EXCEEDED	0.00 s	details
#22	OUTPUT LIMIT EXCEEDED	0.00 s	details
#23	OUTPUT LIMIT EXCEEDED	0.00 s	details
#24	OUTPUT LIMIT EXCEEDED	0.00 s	details
#25	OUTPUT LIMIT EXCEEDED	0.00 s	details
#26	OUTPUT LIMIT EXCEEDED	0.00 s	details
#27	OUTPUT LIMIT EXCEEDED	0.00 s	details
#28	OUTPUT LIMIT EXCEEDED	0.00 s	details
#29	OUTPUT LIMIT EXCEEDED	0.00 s	details
#30	OUTPUT LIMIT EXCEEDED	0.00 s	details
#31	OUTPUT LIMIT EXCEEDED	0.00 s	details
#32	OUTPUT LIMIT EXCEEDED	0.00 s	details
#33	OUTPUT LIMIT EXCEEDED	0.00 s	details
#34	OUTPUT LIMIT EXCEEDED	0.00 s	details
#35	OUTPUT LIMIT EXCEEDED	0.00 s	details
#36	OUTPUT LIMIT EXCEEDED	0.00 s	details
#37	OUTPUT LIMIT EXCEEDED	0.00 s	details
#38	OUTPUT LIMIT EXCEEDED	0.00 s	details
#39	OUTPUT LIMIT EXCEEDED	0.00 s	details
#40	OUTPUT LIMIT EXCEEDED	0.00 s	details
#41	OUTPUT LIMIT EXCEEDED	0.00 s	details
#42	OUTPUT LIMIT EXCEEDED	0.00 s	details
#43	OUTPUT LIMIT EXCEEDED	0.00 s	details
#44	OUTPUT LIMIT EXCEEDED	0.00 s	details
#45	OUTPUT LIMIT EXCEEDED	0.00 s	details
#46	OUTPUT LIMIT EXCEEDED	0.00 s	details
#47	OUTPUT LIMIT EXCEEDED	0.00 s	details
#48	OUTPUT LIMIT EXCEEDED	0.00 s	details
#49	OUTPUT LIMIT EXCEEDED	0.00 s	details
#50	OUTPUT LIMIT EXCEEDED	0.00 s	details
#51	OUTPUT LIMIT EXCEEDED	0.00 s	details
#52	OUTPUT LIMIT EXCEEDED	0.00 s	details
#53	OUTPUT LIMIT EXCEEDED	0.00 s	details

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:144:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < thunder.size(); ++i) {
                                   ^
input/code.cpp: In function 'Treap* rightmost(Treap*)':
input/code.cpp:87:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
input/code.cpp: In function 'Treap* leftmost(Treap*)':
input/code.cpp:93:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

Code

#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
#include <stdlib.h>

struct Treap {
	Treap* left;
	Treap* right;
	int start;
	int end;
	int start_last_update;
	int end_last_update;
	int value;

	Treap(int s, int e, int t) {
		start = s;
		end = e;
		start_last_update = t;
		end_last_update = t;
		left = 0;
		right = 0;
		value = rand();
	}
};

// Join left and right into result
void join(Treap*& result, Treap*& left, Treap*& right) {
	if (left == 0) {
		result = right;
	} else if (right == 0) {
		result = left;
	} else {
		if (left->value > right->value) {
			result = left;
			join(left->right, left->right, right);
		} else {
			result = right;
			join(right->left, left, right->left);
		}
	}
}

// Split source into left and right
void split(Treap*& left, Treap*& right, Treap* source, bool comp_end, int comp) {
	if (source == 0) {
		left = 0;
		right = 0;
	} else {
		bool go_left = false;
		if (comp_end) {
			if (source->end < comp) {
				go_left = true;
			} else {
				go_left = false;
			}
		} else {
			if (source->start <= comp) {
				go_left = true;
			} else {
				go_left = false;
			}
		}
		if (go_left) {
			left = source;
			split(left->right, right, source->right, comp_end, comp);
		} else {
			right = source;
			split(left, right->left, source->left, comp_end, comp);
		}
	}
}

void print(Treap* source) {
	if (source != 0) {
		std::cout << source->start << ' ' << source->end << ' ' << source->start_last_update << ' ' << source->end_last_update << ' ' << source->value << '\n';
		print(source->left);
		print(source->right);
	}
}

// Find rightmost node in treap
Treap* rightmost(Treap* source) {
	if (source == 0) return 0;
	Treap* rec = rightmost(source->right);
	if (rec == 0) return source;
}
// Find leftmost node in treap
Treap* leftmost(Treap* source) {
	if (source == 0) return 0;
	Treap* rec = leftmost(source->left);
	if (rec == 0) return source;
}

Treap* left_of(Treap* source, int comp) {
	if (source == 0) return 0;
	if (source->start <= comp) {
		Treap* rec = left_of(source->right, comp);
		if (rec == 0) {
			return source;
		} else {
			return rec;
		}
	} else {
		return left_of(source->left, comp);
	}
}
Treap* right_of(Treap* source, int comp) {
	if (source == 0) return 0;
	if (comp <= source->end) {
		Treap* rec = right_of(source->left, comp);
		if (rec == 0) {
			return source;
		} else {
			return rec;
		}
	} else {
		return right_of(source->right, comp);
	}
}

const int N = 2 * (1e5);
bool can [N];
std::vector<std::pair<int, std::pair<int, int>>> thunder;

int main() {
	int n;
	std::cin >> n;
	for (int i = 0; i < n; ++i) {
		int x, r, t;
		std::cin >> t >> x >> r;
		thunder.push_back({t, {-r, x}});
	}
	int s;
	std::cin >> s;
	for (int i = 1; i <= s; ++i) {
		int t, x;
		std::cin >> t >> x;
		thunder.push_back({t, {i, x}});
	}
	std::sort(thunder.begin(), thunder.end());
	// Idea: store all intervals in a treap, and lazy update.
	Treap* root = new Treap(0, 0, 0);
	for (int i = 0; i < thunder.size(); ++i) {
		std::cout << "Event " << i << '\n';
		print(root);
		auto e = thunder[i];
		int t = e.first;
		int x = e.second.second;
		if (e.second.first > 0) {
			int ind = e.second.first - 1;
			std::cout << "question " << t << ' ' << x << ' ' << ind << '\n';
			Treap* left = left_of(root, x);
			Treap* right = right_of(root, x);
			if ((left != 0) && (left->end + t - left->end_last_update >= x)) {
				can[ind] = true;
			}
			if ((right != 0) && (right->start - t + right->start_last_update <= x)) {
				can[ind] = true;
			}
		} else {
			int rad = -1 - e.second.first;
			std::cout << "thunder " << t << ' ' << x << ' ' << rad << '\n';
			Treap* left = 0; Treap* mid = 0; Treap* right = 0;
			split(left, mid, root, true, x - rad);
			split(mid, right, mid, false, x + rad);
			Treap* left_right = rightmost(left);
			Treap* center_left = leftmost(mid);
			Treap* center_right = rightmost(mid);
			Treap* right_left = leftmost(right);

			// Make area left of strike
			int min_start = -1e9;
			if (left_right != 0) {
				left_right->end = std::min(x - rad - 1, left_right->end + t - left_right->end_last_update);
				left_right->end_last_update = t;
				min_start = left_right->end + 1;
			}
			if (center_left != 0) {
				int start = std::max(min_start, center_left->start - t + center_left->start_last_update);
				int end = x - rad - 1;
				if (start <= end) {
					Treap* elem = new Treap(start, end, t);
					join(left, left, elem);
				}
			} else if (right_left != 0) {
				int start = std::max(min_start, right_left->start - t + right_left->start_last_update);
				int end = x - rad - 1;
				if (start <= end) {
					Treap* elem = new Treap(start, end, t);
					join(left, left, elem);
				}
				right_left->start = std::max(start, x + rad + 1);
				right_left->start_last_update = t;
			}

			int max_end = 1e9;
			if (right_left != 0) {
				right_left->start = std::max(x + rad + 1, right_left->start - t + right_left->start_last_update);
				right_left->start_last_update = t;
				max_end = right_left->start - 1;
			}
			if (center_right != 0) {
				int start = x + rad + 1;
				int end = std::min(max_end, center_right->end + t - center_right->end_last_update);
				if (start <= end) {
					Treap* elem = new Treap(start, end, t);
					join(right, elem, right);
				}
			} else if (left_right != 0) {
				int start = x + rad + 1;
				int end = std::min(max_end, left_right->end + t - left_right->end_last_update);
				if (start <= end) {
					Treap* elem = new Treap(start, end, t);
					join(right, elem, right);
				}
				left_right->end = std::min(start, x - rad - 1);
				left_right->end_last_update = t;
			}
			join(root, left, right);
		}
	}
	std::cout << "END!\n";
	print(root);
	for (int i = 0; i < s; ++i) {
		std::cout << (can[s] ? "@" : "*");
	}
	std::cout << '\n';
}

Test details

Test 1

Verdict: OUTPUT LIMIT EXCEEDED

input
`40000 103463246 -141864454 26289 400364460 610226101 2798 372074921 -198366857 9770 455300963 10139032 440 ...` view save

correct output
`@@@@@@@@@@@@*@...` view save

user output
(empty)

Test 2

Verdict: OUTPUT LIMIT EXCEEDED

input
`39400 334 -88 2 148 -142 1 220 58 2 126 -120 2 ...` view save

correct output
`@**@@@@@*@@@@@****...` view save

user output
(empty)

Test 3

Verdict: OUTPUT LIMIT EXCEEDED

input
`39400 642 172 2 526 176 2 526 -120 2 56 -54 2 ...` view save

correct output
`@*****@@@**@@@**...` view save

user output
(empty)

Test 4

Verdict: OUTPUT LIMIT EXCEEDED

input
`80008 11021917 43648 611 7971207 57751 142 29320129 43987 146 2165415 -1181 298 ...` view save

correct output
`@@@*@@@@@@@@@@@@@**@@@...` view save

user output
(empty)

Test 5

Verdict: OUTPUT LIMIT EXCEEDED

input
`3940 1660 -240 20 1400 140 20 400 700 20 480 -340 20 ...` view save

correct output
`****@*********************...` view save

user output
(empty)

Test 6

Verdict: OUTPUT LIMIT EXCEEDED

input
`3940 1500 -200 20 1560 -620 16 480 -340 14 1160 180 20 ...` view save

correct output
`@@@@@*@@*@@@**@@...` view save

user output
(empty)

Test 7

Verdict: OUTPUT LIMIT EXCEEDED

input
`6727 1210101 -15564 267 1075205 -10459 166 313388 -9943 179 1805862 -23623 253 ...` view save

correct output
`@@@@@@@@@@@**@@@@@@@**...` view save

user output
(empty)

Test 8

Verdict: WRONG ANSWER

input
`6714 377971 728 589 3432270 54599 103 2427212 27539 483 1201529 6090 493 ...` view save

correct output
`@@@@@@@@@@@@@@@@**@@...` view save

user output
`Event 0 0 0 0 0 1804289383 thunder 488 -341 146 Event 1 -194 0 488 0 1804289383 ...` view save

Test 9

Verdict: OUTPUT LIMIT EXCEEDED

input
`6745 341217 -5114 315 791102 -240 92 1119566 -1755 75 1201486 -584 18 ...` view save

correct output
`@@@@@@@@@@@@@@@@@@@@@@...` view save

user output
(empty)

Test 10

Verdict: OUTPUT LIMIT EXCEEDED

input
`6709 2529591 44866 237 2924365 29731 662 970844 26104 588 1627200 60475 47 ...` view save

correct output
`@@@**@@@@@@@@@@@@@@@@@@@*@...` view save

user output
(empty)

Test 11

Verdict: OUTPUT LIMIT EXCEEDED

input
`6689 1334590 -10356 742 974219 12983 108 3354325 -46823 38 1181441 10535 34 ...` view save

correct output
`@@@@@@@@@@@@*@@@@@@@@@@@...` view save

user output
(empty)

Test 12

Verdict: OUTPUT LIMIT EXCEEDED

input
`25 0 -3 1 9 12 2 12 -3 3 9 -12 1 ...` view save

correct output
`@**@****@@@*@***...` view save

user output
(empty)

Test 13

Verdict: OUTPUT LIMIT EXCEEDED

input
`25 12 -15 3 6 9 3 12 9 3 6 -15 3 ...` view save

correct output
`@***********@************@...` view save

user output
(empty)

Test 14

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 12 9 3 3 0 1 12 3 2 6 3 1 ...` view save

correct output
`******@@@@******@@@@*@...` view save

user output
(empty)

Test 15

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 0 -3 3 3 -12 3 3 6 3 12 9 3 ...` view save

correct output
`******@*@**********@...` view save

user output
(empty)

Test 16

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 9 -6 3 6 -3 3 0 9 3 3 -12 3 ...` view save

correct output
`***************@@*@*****...` view save

user output
(empty)

Test 17

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 6 -3 3 0 3 2 0 -15 2 3 12 2 ...` view save

correct output
`**@@@@***@**@@@@...` view save

user output
(empty)

Test 18

Verdict: OUTPUT LIMIT EXCEEDED

input
`25 4 -10 2 8 6 2 6 4 1 6 0 1 ...` view save

correct output
`@***@@@*********@@******...` view save

user output
(empty)

Test 19

Verdict: OUTPUT LIMIT EXCEEDED

input
`25 6 -4 2 6 8 2 4 6 2 8 -6 2 ...` view save

correct output
`@**********@@@************...` view save

user output
(empty)

Test 20

Verdict: OUTPUT LIMIT EXCEEDED

input
`16 9 6 3 3 -6 3 3 6 3 9 0 3 ...` view save

correct output
`*******************@******...` view save

user output
(empty)

Test 21

Verdict: OUTPUT LIMIT EXCEEDED

input
`16 0 3 3 6 3 1 6 -9 3 0 -9 2 ...` view save

correct output
`*@**@@@@@@@@@*...` view save

user output
(empty)

Test 22

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 12 3 3 0 -9 3 3 6 3 9 6 3 ...` view save

correct output
`****@*@****@@*****...` view save

user output
(empty)

Test 23

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 0 -3 2 6 -9 1 12 3 2 3 -6 2 ...` view save

correct output
`@@***@@@@@@********@...` view save

user output
(empty)

Test 24

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 6 -9 3 6 3 3 6 -3 3 0 -3 3 ...` view save

correct output
`***********@**************...` view save

user output
(empty)

Test 25

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 0 -9 3 0 3 2 0 9 3 3 -6 2 ...` view save

correct output
`@**@@***********@*...` view save

user output
(empty)

Test 26

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 0 -6 2 8 2 2 0 2 2 8 6 2 ...` view save

correct output
`****@@@**@@@@@***@...` view save

user output
(empty)

Test 27

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 2 -4 1 4 -2 2 2 4 2 0 6 2 ...` view save

correct output
`*@@@**@@@@********...` view save

user output
(empty)

Test 28

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 0 -2 2 4 2 1 6 -4 1 4 -6 2 ...` view save

correct output
`*@@*@**********@@@**...` view save

user output
(empty)

Test 29

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 2 -8 2 4 -10 2 2 8 2 0 -2 2 ...` view save

correct output
`**@**************@****...` view save

user output
(empty)

Test 30

Verdict: OUTPUT LIMIT EXCEEDED

input
`12 6 -9 1 0 3 3 6 3 2 6 -3 3 ...` view save

correct output
`**@@@@@@*@@@@@@@...` view save

user output
(empty)

Test 31

Verdict: OUTPUT LIMIT EXCEEDED

input
`12 3 0 3 6 -3 3 6 3 3 3 6 3 ...` view save

correct output
`*@******@*************...` view save

user output
(empty)

Test 32

Verdict: OUTPUT LIMIT EXCEEDED

input
`12 6 9 1 0 -3 2 3 -12 1 3 6 2 ...` view save

correct output
`****@@@*@***********...` view save

user output
(empty)

Test 33

Verdict: OUTPUT LIMIT EXCEEDED

input
`12 6 3 3 3 6 3 0 -9 3 0 9 3 ...` view save

correct output
`@***@***********@*****...` view save

user output
(empty)

Test 34

Verdict: OUTPUT LIMIT EXCEEDED

input
`16 6 4 2 6 -8 2 2 -8 2 2 4 1 ...` view save

correct output
`****@@********@@**...` view save

user output
(empty)

Test 35

Verdict: OUTPUT LIMIT EXCEEDED

input
`16 4 2 2 6 0 2 2 4 2 2 -4 2 ...` view save

correct output
`**@@*@@@@*@*****...` view save

user output
(empty)

Test 36

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 2 4 2 0 -2 2 8 2 2 2 0 2 ...` view save

correct output
`***@@****@@@@@...` view save

user output
(empty)

Test 37

Verdict: OUTPUT LIMIT EXCEEDED

input
`25 0 -3 1 4 -1 1 1 -4 1 4 -5 1 ...` view save

correct output
`**@**@@@@@***@******...` view save

user output
(empty)

Test 38

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 0 -2 2 4 -6 1 4 2 1 2 0 1 ...` view save

correct output
`@@@@@@@@******@@...` view save

user output
(empty)

Test 39

Verdict: OUTPUT LIMIT EXCEEDED

input
`25 3 2 1 2 1 1 2 -5 1 1 -4 1 ...` view save

correct output
`******@*@@@**@@@...` view save

user output
(empty)

Test 40

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 2 -8 1 4 6 1 2 8 1 4 -10 2 ...` view save

correct output
`@************@*@***@...` view save

user output
(empty)

Test 41

Verdict: OUTPUT LIMIT EXCEEDED

input
`15 0 6 2 4 -2 2 0 -6 2 2 8 2 ...` view save

correct output
`@*****@*@******@...` view save

user output
(empty)

Test 42

Verdict: OUTPUT LIMIT EXCEEDED

input
`10 6 3 3 9 -6 3 0 3 3 0 -3 3 ...` view save

correct output
`*@@@*@*******@****...` view save

user output
(empty)

Test 43

Verdict: OUTPUT LIMIT EXCEEDED

input
`10 9 -6 1 0 3 1 6 3 1 3 0 3 ...` view save

correct output
`@@*@@@@@@@@@@@@@@@...` view save

user output
(empty)

Test 44

Verdict: OUTPUT LIMIT EXCEEDED

input
`10 3 6 2 0 -15 1 3 12 1 0 -9 2 ...` view save

correct output
`******************************...` view save

user output
(empty)

Test 45

Verdict: OUTPUT LIMIT EXCEEDED

input
`10 0 9 3 3 6 3 3 0 3 3 12 3 ...` view save

correct output
`*****************************@...` view save

user output
(empty)

Test 46

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 2 -3 1 4 -1 1 3 -4 1 1 2 1 ...` view save

correct output
`@*@@**********@@****@@...` view save

user output
(empty)

Test 47

Verdict: OUTPUT LIMIT EXCEEDED

input
`20 1 -2 1 1 0 1 2 -1 1 2 1 1 ...` view save

correct output
`*@@@@@**@@@@@*...` view save

user output
(empty)

Test 48

Verdict: OUTPUT LIMIT EXCEEDED

input
`9 6 -3 3 0 3 3 0 -9 3 0 -3 3 ...` view save

correct output
`*************@@***********...` view save

user output
(empty)

Test 49

Verdict: OUTPUT LIMIT EXCEEDED

input
`9 6 -3 3 3 -6 2 6 -9 2 0 -9 2 ...` view save

correct output
`**@@*******@@@********...` view save

user output
(empty)

Test 50

Verdict: OUTPUT LIMIT EXCEEDED

input
`12 4 -2 2 2 -4 2 0 -2 2 2 4 2 ...` view save

correct output
`*@@************@*@**...` view save

user output
(empty)

Test 51

Verdict: OUTPUT LIMIT EXCEEDED

input
`200000 6 -153069114 2 4 957747793 2 3 649760492 1 7 25202362 2 ...` view save

correct output
`@@@@@@@@@@@@*@@@@@@@@@...` view save

user output
(empty)

Test 52

Verdict: OUTPUT LIMIT EXCEEDED

input
`200000 187172 -153069114 2 36921 957747793 2 114661 649760492 1 185526 25202362 2 ...` view save

correct output
`******************************...` view save

user output
(empty)

Test 53

Verdict: OUTPUT LIMIT EXCEEDED

input
`200000 999710767 -2720510 1230 999894078 -5196572 2343 999960423 1742266 2686 999907359 588714 3637 ...` view save

correct output
`@@@@@@@@@@@@@***@@@@@@@@@@...` view save

user output
(empty)

KILO 2017 2/5

Evacuation

Compiler report

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Test 38

Test 39

Test 40

Test 41

Test 42

Test 43

Test 44

Test 45

Test 46

Test 47

Test 48

Test 49

Test 50

Test 51

Test 52

Test 53

Tasks

Submissions (blitzset)