General
 
 
# 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
→ Source
#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';
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details