#include "xylophone.h"
#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, int> m;
int qq(int L, int R) {
if (m[{L, R}] != 0) {
return m[{L, R}];
}
return m[{L, R}] = query(L, R);
}
void solve(int n) {
int l = 1, r = n, idx = r;
while(l <= r) {
int mid = (l + r) / 2;
if (qq(1, mid) != n-1) {
l = mid + 1;
} else {
idx = mid;
r = mid - 1;
}
}
vector<bool> seen(n+5, false);
vector<int> an(n+5, -1);
an[idx] = n;
for(int i = idx-1; i >= 1; i--) {
int val = qq(i, idx);
if (!seen[val]) {
an[i] = n - val;
seen[val] = true;
}
}
for(int i = idx+1; i <= n; i++) {
int val = qq(idx, i);
if (!seen[val]) {
an[i] = n - val;
seen[val] = true;
}
}
for(int i = idx; i > 1; i--) {
assert(an[i] != -1);
if (an[i-1] != -1) continue;
int val = qq(i-1, i);
an[i-1] = an[i] + val;
}
for(int i = idx; i < n; i++) {
assert(an[i] != -1);
if (an[i+1] != -1) continue;
int val = qq(i, i+1);
an[i+1] = an[i] + val;
}
for(int i = 1; i <= n; i++) {
answer(i, an[i]);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Wrong Answer [4] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Wrong Answer [4] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
364 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Incorrect |
1 ms |
364 KB |
Wrong Answer [4] |
4 |
Halted |
0 ms |
0 KB |
- |