#include <iostream>
#include "xylophone.h"
using namespace std;
const int maxN = 6e3 + 226;
int val[maxN], abd[maxN];
void solve(int N){
int maxAt, l = 0, r = N, m;
while(l + 1 < r){
m = (l + r) / 2;
if(query(1, m) == N - 1){
r = m;
} else {
l = m;
}
}
maxAt = r;
val[maxAt] = N;
//cout << "Maxat = " << maxAt << endl;
if(maxAt < N){
val[maxAt + 1] = N - query(maxAt, maxAt + 1);
//cout << "val[" << maxAt + 1 << "] = " << val[maxAt + 1] << endl;
}
if(maxAt > 1){
val[maxAt - 1] = N - query(maxAt - 1, maxAt);
//cout << "val[" << maxAt - 1 << "] = " << val[maxAt - 1] << endl;
}
int currentEx = maxAt, cur = N - val[maxAt + 1], type = -1; //-1: currently at maxima, else currently at minima
for(int i = maxAt + 2; i <= N; i++){
int r = query(currentEx, i);
if(r > cur){
val[i] = val[currentEx] + type * r;
cur = r;
} else {
currentEx = i - 1;
type *= -1;
cur = r = query(currentEx, i);
val[i] = val[currentEx] + type * r;
}
}
currentEx = maxAt, cur = N - val[maxAt - 1], type = -1;
for(int i = maxAt - 2; i; i--){
int r = query(i, currentEx);
//cout << "currentEx = " << currentEx << ", i = " << i << ", r = " << r << endl;
if(r > cur){
val[i] = val[currentEx] + type * r;
cur = r;
} else {
currentEx = i + 1;
type *= -1;
cur = r = query(i, currentEx);
val[i] = val[currentEx] + type * r;
}
}
for(int i = 1; i <= N; i++){
//cout << "val[" << i << "] = " << val[i] << endl;
answer(i, val[i]);
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
248 KB |
Output is correct |
3 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [7] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
248 KB |
Output is correct |
3 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [7] |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
5 ms |
248 KB |
Output is correct |
3 |
Incorrect |
5 ms |
376 KB |
Wrong Answer [7] |
4 |
Halted |
0 ms |
0 KB |
- |