# |
Author |
Problem |
Lang |
Verdict |
Time |
Memory |
Sent |
Judged |
|
72965891 |
Practice:
grphil |
1322E
- 33
|
GNU C++11
|
Accepted
|
530 ms
|
82404 KB
|
2020-03-11 18:27:03 |
2020-03-11 18:27:03 |
|
#include <bits/stdc++.h>
using namespace std;
const int maxx = 2000000;
int s[maxx];
int ans[maxx];
int an = 0;
deque<int> mn;
deque<int> mx;
int lf[maxx][3];
int rt[maxx][3];
int ann[maxx];
int anl[maxx];
bool t[maxx];
inline void work(int i, int mm[maxx][3]) {
if (t[i]) {
while (mn.size() > 0 && s[mn.back()] > s[i]) {
mn.pop_back();
}
if (mn.size() > 0) {
mm[i][2] = mn.back();
}
while (mn.size() > 0 && s[mn.back()] == s[i]) {
mn.pop_back();
}
if (mn.size() > 0) {
mm[i][0] = mn.back();
}
while (mx.size() > 0 && s[mx.front()] >= s[i]) {
if (mx.size() < 2 || s[mx[1]] < s[i]) {
break;
}
mx.pop_front();
}
if (mx.size() > 0 && s[mx.front()] >= s[i]) {
mm[i][1] = mx.front();
}
mn.push_back(i);
} else {
while (mx.size() > 0 && s[mx.back()] < s[i]) {
mx.pop_back();
}
if (mx.size() > 0) {
mm[i][2] = mx.back();
}
while (mx.size() > 0 && s[mx.back()] == s[i]) {
mx.pop_back();
}
if (mx.size() > 0) {
mm[i][0] = mx.back();
}
while (mn.size() > 0 && s[mn.front()] <= s[i]) {
if (mn.size() < 2 || s[mn[1]] > s[i]) {
break;
}
mn.pop_front();
}
if (mn.size() > 0 && s[mn.front()] <= s[i]) {
mm[i][1] = mn.front();
}
mx.push_back(i);
}
}
void pl(int a) {
if (t[a]) {
s[a] = -1;
} else {
s[a] = 1e9;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n;
cin >> n;
for (int i = 2; i < n + 2; i++) {
cin >> s[i];
}
s[1] = s[2];
s[n + 2] = s[n + 1];
int l = 1;
int r = 0;
for (int ii = 2; ii < n + 2; ii++) {
if (s[ii] > s[ii - 1] && s[ii] > s[ii + 1]) {
t[ii] = 1;
continue;
} else if (s[ii] < s[ii - 1] && s[ii] < s[ii + 1]) {
t[ii] = 0;
continue;
}
r = ii;
// cout << l << ' ' << r << '\n';
if (l + 1 == r) {
ans[r] = s[r];
l = r;
continue;
}
ans[l] = 0;
t[l] = !t[l + 1];
t[l - 1] = t[l + 1];
t[l - 2] = t[l];
pl(l - 1);
pl(l - 2);
int rr = s[r + 1];
int rrr = s[r + 2];
t[r] = !t[r - 1];
t[r + 1] = t[r - 1];
t[r + 2] = t[r];
pl(r + 1);
pl(r + 2);
for (int i = l - 2; i <= r + 2; i++) {
lf[i][0] = lf[i][1] = lf[i][2] = -maxx;
rt[i][0] = rt[i][1] = rt[i][2] = maxx;
}
mn.clear();
mx.clear();
for (int i = l - 2; i <= r + 2; i++) {
work(i, lf);
}
mn.clear();
mx.clear();
for (int i = r + 2; i >= l - 2; i--) {
work(i, rt);
}
for (int i = l; i <= r; i++) {
// cout << i << ' ' << an << '\n' << lf[i][0] << ' ' << lf[i][1] << ' ' << lf[i][2] << '\n' << rt[i][0] << ' ' << rt[i][1] << ' ' << rt[i][2] << '\n';
if (lf[i][0] > lf[i][1] && rt[i][0] < rt[i][1]) {
// cout << 0 << '\n';
continue;
}
if (lf[i][0] <= lf[i][1] && rt[i][0] >= rt[i][1]) {
// cout << 1 << '\n';
anl[i] = (i + lf[i][1] + 1) / 2;
if (lf[i][2] > lf[i][1]) {
ann[i] = ann[lf[i][2]];
anl[i] = anl[lf[i][2]];
} else {
ann[i] = i - anl[i];
}
if (rt[i][2] < rt[i][1]) {
continue;
}
int rb = (i + rt[i][1] + 1) / 2;
an = max(an, max(ann[i], rb - i - 1) + (rb - anl[i] - abs(rb - i - 1 - ann[i])) / 2);
for (int j = anl[i]; j < rb; j++) {
ans[j] = s[i];
}
}
if (lf[i][0] > lf[i][1] && rt[i][0] >= rt[i][1]) {
// cout << 2 << '\n';
if (rt[i][2] < rt[i][1] && s[rt[i][2]] == s[i]) continue;
int a = lf[i][0];
assert(rt[a][1] < rt[a][0]);
int b = (rt[a][1] + a + 1) / 2;
an = max(an, b - a - (rt[i][1] - rt[a][1]) / 2 - 2);
for (int j = b + (rt[i][1] - rt[a][1]) / 2; j < (rt[i][1] + i + 1) / 2; j++) {
ans[j] = s[i];
}
}
if (lf[i][0] <= lf[i][1] && rt[i][0] < rt[i][1]) {
// cout << 3 << '\n';
if (lf[i][2] > lf[i][1] && s[lf[i][2]] == s[i]) continue;
int a = rt[i][0];
assert(lf[a][1] >= lf[a][0]);
int b = (a + lf[a][1] + 1) / 2;
an = max(an, a - b + (lf[a][1] - lf[i][1]) / 2 - 1);
for (int j = (i + lf[i][1] + 1) / 2; j < b - (lf[a][1] - lf[i][1]) / 2; j++) {
ans[j] = s[i];
}
}
}
s[r + 1] = rr;
s[r + 2] = rrr;
l = r;
}
cout << an << '\n';
for (int i = 2; i <= n + 1; i++) {
cout << ans[i] << ' ';
}
cout << '\n';
}
Click to see test details