QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#243927 | #6400. Game: Celeste | ucup-team1198 | TL | 1589ms | 169696kb | C++20 | 4.3kb | 2023-11-08 19:20:09 | 2023-11-08 19:20:09 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define ld long double
#define all(a) (a).begin(), (a).end()
const int K = 20;
const int MAXN = 1 << K;
map<pair<int, int>, int> nodes_by_children[K + 1];
vector<pair<int, int>> nodes[K + 1];
bool cmp(int rk, int tree1, int tree2) {
if (tree1 == tree2)
return false;
if (rk == 0)
return tree1 < tree2;
if (nodes[rk][tree1].second != nodes[rk][tree2].second) {
return cmp(rk - 1, nodes[rk][tree1].second, nodes[rk][tree2].second);
}
return cmp(rk - 1, nodes[rk][tree1].first, nodes[rk][tree2].first);
}
int add_one(int tree, int rk, int left, int right, int i) {
if (left + 1 == right) {
return tree + 1;
}
int l1 = nodes[rk][tree].first;
int r1 = nodes[rk][tree].second;
int mid = (left + right) / 2;
if (i < mid)
l1 = add_one(l1, rk - 1, left, mid, i);
else
r1 = add_one(r1, rk - 1, mid, right, i);
if (nodes_by_children[rk].count(make_pair(l1, r1)))
return nodes_by_children[rk][make_pair(l1, r1)];
nodes[rk].emplace_back(l1, r1);
nodes_by_children[rk][make_pair(l1, r1)] = nodes[rk].size() - 1;
return nodes[rk].size() - 1;
}
void restore_ans(int tree, int rk, int left, int right, vector<int>& ans) {
if (left + 1 == right) {
for (int j = 0; j < tree; ++j)
ans.emplace_back(left);
return;
}
int mid = (left + right) / 2;
restore_ans(nodes[rk][tree].second, rk - 1, mid, right, ans);
restore_ans(nodes[rk][tree].first, rk - 1, left, mid, ans);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
for (int i = 1; i <= K; ++i) {
nodes[i].emplace_back(0, 0);
nodes_by_children[i][make_pair(0, 0)] = 0;
}
while (t--) {
int n, L, R;
cin >> n >> L >> R;
vector<int> x(n);
for (int i = 0; i < n; ++i)
cin >> x[i];
vector<int> a(n);
for (int i = 0; i < n; ++i)
cin >> a[i];
int cur_rk = 0;
while ((1 << cur_rk) <= n)
++cur_rk;
vector<int> dp(n, -1);
dp[0] = add_one(0, cur_rk, 0, 1 << cur_rk, a[0]);
vector<int> stack1;
vector<int> mx1;
vector<int> stack2;
vector<int> mx2;
auto queue_push = [&](int x) {
stack2.emplace_back(x);
if (mx2.empty() || cmp(cur_rk, mx2.back(), x))
mx2.emplace_back(x);
else
mx2.emplace_back(mx2.back());
};
auto queue_pop = [&]() {
if (stack1.empty()) {
while (!stack2.empty()) {
int x = stack2.back();
stack1.emplace_back(x);
if (mx1.empty() || cmp(cur_rk, mx1.back(), x))
mx1.emplace_back(x);
else
mx1.emplace_back(mx1.back());
stack2.pop_back();
mx2.pop_back();
}
}
stack1.pop_back();
mx1.pop_back();
};
int l1 = 0, r1 = 0;
for (int i = 1; i < n; ++i) {
while (r1 < i && x[r1] <= x[i] - L) {
if (dp[r1] != -1)
queue_push(dp[r1]);
++r1;
}
while (l1 < i && x[l1] < x[i] - R) {
if (dp[l1] != -1)
queue_pop();
++l1;
}
if (stack1.empty() && stack2.empty()) {
dp[i] = -1;
} else {
int opt = -1;
if (stack2.empty())
opt = mx1.back();
else if (stack1.empty())
opt = mx2.back();
else if (cmp(cur_rk, mx1.back(), mx2.back()))
opt = mx2.back();
else
opt = mx1.back();
dp[i] = add_one(opt, cur_rk, 0, 1 << cur_rk, a[i]);
}
}
if (dp[n - 1] == -1)
cout << -1 << '\n';
else {
vector<int> ans;
restore_ans(dp[n - 1], cur_rk, 0, 1 << cur_rk, ans);
cout << ans.size() << '\n';
for (int x : ans)
cout << x << ' ';
cout << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3592kb
input:
2 5 2 3 1 2 3 4 5 5 2 3 1 4 3 1 2 1 4 7 3 3 3
output:
3 5 4 3 -1
result:
ok 3 lines
Test #2:
score: 0
Accepted
time: 1589ms
memory: 169696kb
input:
10000 57 8 11 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 11 16 7 7 10 13 9 14 10 1 12 4 8 13 3 20 16 7 16 19 20 8 19 7 16 6 17 13 7 19 17 11 12 17 6 3 7 8 14 2 4 15 5 18 16 7 20 9 1...
output:
7 20 20 19 14 12 11 3 -1 6 6 5 3 2 1 1 -1 185 20 20 20 20 20 20 20 20 19 19 19 19 19 19 19 19 19 19 19 19 18 18 18 18 18 17 17 17 17 17 17 17 17 16 16 16 16 16 16 16 16 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 15 14 14 14 14 14 14 14 13 13 13 13 13 13 13 13 13 12 12 12 12 12 12 12 ...
result:
ok 16378 lines
Test #3:
score: 0
Accepted
time: 505ms
memory: 22976kb
input:
10000 86 230405 991217 3291 11742 17120 30018 47955 52215 96227 98031 100118 106944 117304 121905 124796 135037 164100 164654 169459 177527 206513 212554 228740 229590 261521 295062 300116 312030 326533 329513 349983 353580 355242 356731 363347 368753 389545 396163 399755 409927 426532 427781 441386...
output:
4 20 19 2 1 4 19 12 6 3 -1 -1 24 20 19 18 18 18 18 18 18 18 18 16 16 16 16 15 15 13 12 11 9 5 4 2 2 -1 2 4 3 3 6 4 2 4 13 12 5 5 3 20 17 5 3 20 8 3 -1 -1 1 1 -1 5 20 20 19 15 14 2 13 12 -1 -1 4 20 20 8 5 -1 -1 -1 6 20 16 16 16 13 9 -1 -1 -1 3 19 17 11 3 19 15 9 -1 -1 -1 -1 -1 -1 2 7 3...
result:
ok 14975 lines
Test #4:
score: 0
Accepted
time: 1523ms
memory: 142220kb
input:
10000 101 17 17 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98...
output:
-1 15 10 10 10 10 10 10 9 9 9 9 7 7 6 6 3 -1 44 10 10 10 10 10 10 10 10 10 10 10 9 9 9 9 9 9 9 9 9 9 9 9 9 9 9 8 8 8 8 7 6 6 6 6 6 6 6 5 4 3 3 3 3 11 10 10 10 10 10 9 8 7 6 6 2 6 10 10 10 10 8 3 18 10 10 10 10 10 10 8 8 8 8 7 7 7 6 5 3 2 2 -1 -1 1 1 -1 -1 -1 20 10 10 10 10 10 10 10 10 10 9 8 8...
result:
ok 16344 lines
Test #5:
score: 0
Accepted
time: 451ms
memory: 10200kb
input:
10000 18 16 16 1 2 3 4 5 6 7 8 10 11 12 13 14 16 17 18 19 20 2 2 2 1 2 1 1 2 2 2 2 1 2 2 1 2 1 1 403 3 7 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 ...
output:
-1 126 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 -1 -1 -1 1 1 -1 -1 10 2 2 2 2 2 2 1 1 1...
result:
ok 16420 lines
Test #6:
score: 0
Accepted
time: 837ms
memory: 16588kb
input:
10000 251 1 1 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 9...
output:
251 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
result:
ok 16925 lines
Test #7:
score: 0
Accepted
time: 949ms
memory: 41936kb
input:
100 23882 222 481 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 ...
output:
102 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 19...
result:
ok 167 lines
Test #8:
score: 0
Accepted
time: 332ms
memory: 11732kb
input:
100 3789 29850 70419 774 1032 1649 1723 2194 3021 3114 3308 3344 3360 3688 3781 3967 4245 4878 4966 5099 5597 5617 5638 5645 5784 5871 6136 6158 6358 6483 6600 6766 6775 6800 6895 7119 7439 7485 7696 7734 8432 8493 8581 8627 9203 9576 9885 10062 10290 10454 10466 10537 10717 10861 11048 11484 11497 ...
output:
30 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 20 19 18 3 -1 -1 -1 4 20 20 18 10 -1 6 20 20 20 20 15 9 -1 -1 5 20 20 20 18 4 4 20 20 13 7 -1 4 20 20 19 18 -1 -1 -1 -1 2 16 8 -1 3 20 20 6 8 20 20 20 20 20 20 15 12 -1 -1 -1 17 20 20 20 20 20 20 20 20 20 20 20...
result:
ok 139 lines
Test #9:
score: 0
Accepted
time: 892ms
memory: 52948kb
input:
100 181 1947 1967 17 23 47 53 55 68 84 92 110 147 153 164 191 198 207 209 215 221 255 269 275 302 305 322 324 363 370 373 385 405 407 429 451 458 466 472 478 500 508 544 557 561 564 565 569 587 600 610 617 630 645 659 665 670 674 715 726 744 747 764 769 770 774 782 786 787 794 795 824 852 860 873 87...
output:
-1 -1 -1 12 10 10 10 10 10 10 10 10 10 10 9 4 12 10 10 10 10 10 10 10 10 10 10 5 5 13 10 10 10 10 10 10 10 10 10 10 10 5 4 -1 22 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 5 2 215 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 ...
result:
ok 166 lines
Test #10:
score: 0
Accepted
time: 536ms
memory: 16916kb
input:
100 5589 851 904 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...
output:
-1 267 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3...
result:
ok 184 lines
Test #11:
score: 0
Accepted
time: 177ms
memory: 5684kb
input:
100 6944 1905 1926 2 3 4 6 7 8 9 10 11 13 15 16 17 18 20 22 23 24 25 29 31 32 33 34 35 39 40 42 43 44 45 46 47 49 51 54 55 57 58 60 61 62 63 64 67 68 69 71 72 74 75 76 78 79 80 81 82 83 84 85 86 90 91 92 94 95 96 98 100 104 105 106 107 108 109 111 112 117 118 119 120 123 125 126 127 128 131 133 134 ...
output:
-1 -1 296 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 118 lines
Test #12:
score: 0
Accepted
time: 923ms
memory: 26388kb
input:
10 93999 762 838 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...
output:
124 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 1 1 2332 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 ...
result:
ok 20 lines
Test #13:
score: 0
Accepted
time: 463ms
memory: 10608kb
input:
10 10628 1687 1731 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97...
output:
-1 -1 76 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 -1 -1 219 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
result:
ok 13 lines
Test #14:
score: 0
Accepted
time: 120ms
memory: 11528kb
input:
3 187063 95635158 95636093 11 507 618 934 1132 2191 3177 3365 3571 3605 4833 4988 5100 6157 6542 7005 7008 7258 7353 7366 7507 9327 10129 10131 10240 11168 11397 12964 13519 14429 14748 15782 16126 16244 16491 17464 17693 18411 19312 19807 19967 20183 21049 21170 21526 21813 22278 22946 23297 23600 ...
output:
-1 -1 -1
result:
ok 3 lines
Test #15:
score: 0
Accepted
time: 242ms
memory: 16768kb
input:
3 109970 343649 521308 4 6 25 27 32 45 53 56 76 81 100 111 115 133 143 145 163 169 173 174 194 199 243 261 299 300 303 311 332 335 341 357 367 368 374 387 392 412 415 422 435 437 442 443 444 454 458 462 466 478 482 486 490 497 499 505 512 521 528 544 549 558 560 574 587 597 620 622 625 643 651 652 6...
output:
3 2 2 1 -1 8 2 2 2 2 2 2 1 1
result:
ok 5 lines
Test #16:
score: 0
Accepted
time: 1050ms
memory: 27016kb
input:
3 541782 286 289 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 9...
output:
1895 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
result:
ok 5 lines
Test #17:
score: -100
Time Limit Exceeded
input:
2 590573 45 48 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 ...