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 <bits/stdc++.h>
#include "xylophone.h"
using namespace std;
int v[5005];
void calc(int l, int r, int p, int m){
if(r <= l)return;
int nm;
if(m == 0)nm = 0;
else nm = 5005;
if(p == 0){
int last = l;
for(int i = l+1; i <= r; i++){
int x = query(l,i);
if(m == 0 && x > nm){//sou min acho max
v[i] = v[l]+x;
nm = x;
calc(last+1,i,1,1);
last = i;
}else if(m == 1 && x < nm){//sou max acho min
v[i] = v[l]-x;
nm = x;
calc(last+1,i,1,0);
last = i;
}
}
if(m == 0)calc(last,r,0,1);
else calc(last,r,0,0);
}else{
int last = r;
for(int i = r-1; i >= l; i--){
int x = query(i,r);
if(m == 0 && x > nm){//sou min acho max
v[i] = v[r]+x;
nm = x;
calc(1,last-1,0,1);
last = i;
}else if(m == 1 && x < nm){//sou max acho min
v[i] = v[r]-x;
nm = x;
calc(1,last-1,0,0);
last = i;
}
}
if(m == 0)calc(l,last,1,1);
else calc(l,last,1,0);
}
}
void solve(int n) {
int l = 1, r = n;
while(l!= r){
int mid = (l+r+1)/2;
if(query(mid,n) == n-1)l = mid;
else r = mid-1;
}
v[l] = 1;
calc(l,n,0,0);
calc(1,l,1,0);
for(int i = 1; i <= n; i++)answer(i,v[i]);
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |