Task: | Evacuation |
Sender: | blitzset |
Submission time: | 2017-09-12 18:59:28 +0300 |
Language: | C++ |
Status: | READY |
Result: | OUTPUT LIMIT EXCEEDED |
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 ... |
correct output |
---|
@@@**@**@@@*@*@**@***@*@***@**... |
user output |
---|
(empty) |
Test 2
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
39400 334 -88 2 148 -142 1 220 58 2 126 -120 2 ... |
correct output |
---|
@****@***@**@*@@**@*@*@*@@****... |
user output |
---|
(empty) |
Test 3
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
39400 642 172 2 526 176 2 526 -120 2 56 -54 2 ... |
correct output |
---|
@*******@****@**@****@**@*@***... |
user output |
---|
(empty) |
Test 4
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
80008 11021917 43648 611 7971207 57751 142 29320129 43987 146 2165415 -1181 298 ... |
correct output |
---|
@*@@***@@@@@@*@@@@*@@**@***@@@... |
user output |
---|
(empty) |
Test 5
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
3940 1660 -240 20 1400 140 20 400 700 20 480 -340 20 ... |
correct output |
---|
******@***********************... |
user output |
---|
(empty) |
Test 6
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
3940 1500 -200 20 1560 -620 16 480 -340 14 1160 180 20 ... |
correct output |
---|
**@***@@@@***@*@**@@*@****@@**... |
user output |
---|
(empty) |
Test 7
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
6727 1210101 -15564 267 1075205 -10459 166 313388 -9943 179 1805862 -23623 253 ... |
correct output |
---|
*@@@@@@@@**@@*@***@@@*@@@*@***... |
user output |
---|
(empty) |
Test 8
Verdict: WRONG ANSWER
input |
---|
6714 377971 728 589 3432270 54599 103 2427212 27539 483 1201529 6090 493 ... |
correct output |
---|
@*@@@***@**@@@**@@@@@**@@@**@@... |
user output |
---|
Event 0 0 0 0 0 1804289383 thunder 488 -341 146 Event 1 -194 0 488 0 1804289383 ... |
Test 9
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
6745 341217 -5114 315 791102 -240 92 1119566 -1755 75 1201486 -584 18 ... |
correct output |
---|
*@@@**@@**@@@*@@@*@@@@@@@*@@@@... |
user output |
---|
(empty) |
Test 10
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
6709 2529591 44866 237 2924365 29731 662 970844 26104 588 1627200 60475 47 ... |
correct output |
---|
@@@***@@@@@*@@*@@@@@*@@@@@@@*@... |
user output |
---|
(empty) |
Test 11
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
6689 1334590 -10356 742 974219 12983 108 3354325 -46823 38 1181441 10535 34 ... |
correct output |
---|
@@@**@@***@*@@@@@@*@@@@@@@@@@@... |
user output |
---|
(empty) |
Test 12
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
25 0 -3 1 9 12 2 12 -3 3 9 -12 1 ... |
correct output |
---|
@****@********@@***@****@*****... |
user output |
---|
(empty) |
Test 13
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
25 12 -15 3 6 9 3 12 9 3 6 -15 3 ... |
correct output |
---|
@*************@**************@... |
user output |
---|
(empty) |
Test 14
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 12 9 3 3 0 1 12 3 2 6 3 1 ... |
correct output |
---|
*******@*@@@********@**@*@*@*@... |
user output |
---|
(empty) |
Test 15
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 0 -3 3 3 -12 3 3 6 3 12 9 3 ... |
correct output |
---|
********@*****@*************@*... |
user output |
---|
(empty) |
Test 16
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 9 -6 3 6 -3 3 0 9 3 3 -12 3 ... |
correct output |
---|
****************@*@***@*******... |
user output |
---|
(empty) |
Test 17
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 6 -3 3 0 3 2 0 -15 2 3 12 2 ... |
correct output |
---|
***@*@@@*****@******@***@**@@*... |
user output |
---|
(empty) |
Test 18
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
25 4 -10 2 8 6 2 6 4 1 6 0 1 ... |
correct output |
---|
@****@*@@***********@@********... |
user output |
---|
(empty) |
Test 19
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
25 6 -4 2 6 8 2 4 6 2 8 -6 2 ... |
correct output |
---|
@************@@@**************... |
user output |
---|
(empty) |
Test 20
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
16 9 6 3 3 -6 3 3 6 3 9 0 3 ... |
correct output |
---|
*********************@********... |
user output |
---|
(empty) |
Test 21
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
16 0 3 3 6 3 1 6 -9 3 0 -9 2 ... |
correct output |
---|
***@******@***@@***@***@@@*@@*... |
user output |
---|
(empty) |
Test 22
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 12 3 3 0 -9 3 3 6 3 9 6 3 ... |
correct output |
---|
******@*****@********@**@*****... |
user output |
---|
(empty) |
Test 23
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 0 -3 2 6 -9 1 12 3 2 3 -6 2 ... |
correct output |
---|
**@**@****@*@@*@**@@*********@... |
user output |
---|
(empty) |
Test 24
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 6 -9 3 6 3 3 6 -3 3 0 -3 3 ... |
correct output |
---|
*************@****************... |
user output |
---|
(empty) |
Test 25
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 0 -9 3 0 3 2 0 9 3 3 -6 2 ... |
correct output |
---|
**@******@@***************@***... |
user output |
---|
(empty) |
Test 26
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 0 -6 2 8 2 2 0 2 2 8 6 2 ... |
correct output |
---|
*****@*@*@*****@@@****@@*****@... |
user output |
---|
(empty) |
Test 27
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 2 -4 1 4 -2 2 2 4 2 0 6 2 ... |
correct output |
---|
**@*@*@*****@**@**@**@********... |
user output |
---|
(empty) |
Test 28
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 0 -2 2 4 2 1 6 -4 1 4 -6 2 ... |
correct output |
---|
**@*@***@**************@**@@**... |
user output |
---|
(empty) |
Test 29
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 2 -8 2 4 -10 2 2 8 2 0 -2 2 ... |
correct output |
---|
****@******************@******... |
user output |
---|
(empty) |
Test 30
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
12 6 -9 1 0 3 3 6 3 2 6 -3 3 ... |
correct output |
---|
***@*@*@@@**@***@*@@**@***@@@*... |
user output |
---|
(empty) |
Test 31
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
12 3 0 3 6 -3 3 6 3 3 3 6 3 ... |
correct output |
---|
***@**********@***************... |
user output |
---|
(empty) |
Test 32
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
12 6 9 1 0 -3 2 3 -12 1 3 6 2 ... |
correct output |
---|
*****@*@**@*****@*************... |
user output |
---|
(empty) |
Test 33
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
12 6 3 3 3 6 3 0 -9 3 0 9 3 ... |
correct output |
---|
@*****@***************@*******... |
user output |
---|
(empty) |
Test 34
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
16 6 4 2 6 -8 2 2 -8 2 2 4 1 ... |
correct output |
---|
******@**@**********@****@****... |
user output |
---|
(empty) |
Test 35
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
16 4 2 2 6 0 2 2 4 2 2 -4 2 ... |
correct output |
---|
***@*@***@****@@**@***@*******... |
user output |
---|
(empty) |
Test 36
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 2 4 2 0 -2 2 8 2 2 2 0 2 ... |
correct output |
---|
*****@****@********@**@@*@**@*... |
user output |
---|
(empty) |
Test 37
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
25 0 -3 1 4 -1 1 1 -4 1 4 -5 1 ... |
correct output |
---|
****@*****@@@*@@*****@********... |
user output |
---|
(empty) |
Test 38
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 0 -2 2 4 -6 1 4 2 1 2 0 1 ... |
correct output |
---|
*@@@*@*@**@**@***@*********@*@... |
user output |
---|
(empty) |
Test 39
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
25 3 2 1 2 1 1 2 -5 1 1 -4 1 ... |
correct output |
---|
********@*****@@***@*****@@@**... |
user output |
---|
(empty) |
Test 40
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 2 -8 1 4 6 1 2 8 1 4 -10 2 ... |
correct output |
---|
@**************@*****@******@*... |
user output |
---|
(empty) |
Test 41
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
15 0 6 2 4 -2 2 0 -6 2 2 8 2 ... |
correct output |
---|
*@********@*****@**********@**... |
user output |
---|
(empty) |
Test 42
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
10 6 3 3 9 -6 3 0 3 3 0 -3 3 ... |
correct output |
---|
***@@**@***@***********@******... |
user output |
---|
(empty) |
Test 43
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
10 9 -6 1 0 3 1 6 3 1 3 0 3 ... |
correct output |
---|
@*@***@*@@@@*@@*@@**@@@***@*@@... |
user output |
---|
(empty) |
Test 44
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
10 3 6 2 0 -15 1 3 12 1 0 -9 2 ... |
correct output |
---|
******************************... |
user output |
---|
(empty) |
Test 45
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
10 0 9 3 3 6 3 3 0 3 3 12 3 ... |
correct output |
---|
*****************************@... |
user output |
---|
(empty) |
Test 46
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 2 -3 1 4 -1 1 3 -4 1 1 2 1 ... |
correct output |
---|
@***@**@***********@*@*****@*@... |
user output |
---|
(empty) |
Test 47
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
20 1 -2 1 1 0 1 2 -1 1 2 1 1 ... |
correct output |
---|
***@***@**@*@**@*****@*@@@*@**... |
user output |
---|
(empty) |
Test 48
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
9 6 -3 3 0 3 3 0 -9 3 0 -3 3 ... |
correct output |
---|
***************@@*************... |
user output |
---|
(empty) |
Test 49
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
9 6 -3 3 3 -6 2 6 -9 2 0 -9 2 ... |
correct output |
---|
***@*@*********@**@*@*********... |
user output |
---|
(empty) |
Test 50
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
12 4 -2 2 2 -4 2 0 -2 2 2 4 2 ... |
correct output |
---|
**@*@**************@*****@****... |
user output |
---|
(empty) |
Test 51
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
200000 6 -153069114 2 4 957747793 2 3 649760492 1 7 25202362 2 ... |
correct output |
---|
*@@@*@@*@@@*@@*@*@**@@@@@@@@*@... |
user output |
---|
(empty) |
Test 52
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
200000 187172 -153069114 2 36921 957747793 2 114661 649760492 1 185526 25202362 2 ... |
correct output |
---|
******************************... |
user output |
---|
(empty) |
Test 53
Verdict: OUTPUT LIMIT EXCEEDED
input |
---|
200000 999710767 -2720510 1230 999894078 -5196572 2343 999960423 1742266 2686 999907359 588714 3637 ... |
correct output |
---|
@@@@*@@@@@@@*@@****@@@@@@@*@@@... |
user output |
---|
(empty) |