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;
static int a[5000];
static int A[5000];
/*
int query(int l, int r) {
int mn = 5000, mx = 0;
for(int i = l; i <= r; i++) {
mn = min(mn, a[i]);
mx = max(mx, a[i]);
}
return mx - mn;
}
void answer(int index, int value) {
A[index] = value;
}
*/
void aaa(int index, int value) {
A[index] = value;
}
void solve(int N) {
// answer index, value
int l = 1, r = N, ans = - 1;
while(l <= r) {
int mid = (l + r) / 2;
if(query(1, mid) == N - 1) {
r = mid - 1;
ans = mid;
}
else {
l = mid + 1;
}
}
aaa(ans, N);
answer(ans, N);
vector<int> p(N + 1, -1);
for(int i = 1; i <= N; i++) {
if(i == ans) {
continue;
}
if(i < ans) {
p[i] = query(i, ans);
}
else {
p[i] = query(ans, i);
}
}
for(int i = ans; i < N; i++) {
if(p[i] == p[i + 1]) {
int u = query(i, i + 1);
// max - min = u
// min = max - u
aaa(i + 1, A[i] + u);
answer(i + 1, A[i] + u);
}
else {
aaa(i + 1, N - p[i + 1]);
answer(i + 1, N - p[i + 1]);
}
}
p[ans] = N;
for(int i = ans - 1; i >= 1; i--) {
if(p[i] == p[i + 1]) {
int u = query(i, i + 1);
aaa(i, A[i + 1] + u);
answer(i, A[i + 1] + u);
}
else {
aaa(i, N - p[i]);
answer(i, N - p[i]);
}
}
}
/*
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i];
}
solve(n);
cout << "\n";
for(int i = 1; i <= n; i++) {
cout << A[i] << " ";
}
}*/
/*
5
2 1 5 3 4
*/
Compilation message (stderr)
xylophone.cpp:5:12: warning: 'a' defined but not used [-Wunused-variable]
5 | static int a[5000];
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |