This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
int getl(int n) {
int l = 1, r = n;
while(l <= r) {
int mid = (l + r) / 2;
if (qq(mid, n) == n-1) {
return mid;
} else {
l = mid + 1;
}
}
}
void solve(int n) {
int l0 = getl(n);
int l = l0, r = n, idx = r;
while(l <= r) {
int mid = (l + r) / 2;
if (qq(l0, 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]);
}
}
Compilation message (stderr)
xylophone.cpp: In function 'int getl(int)':
xylophone.cpp:22:1: warning: control reaches end of non-void function [-Wreturn-type]
22 | }
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |