oj.uz

Submission #72085

# Submission time Handle Problem Language Result Execution time Memory
72085 2018-08-26T05:10:39 Z @younha_holic(#2227, jun6873, rkm0959) Box Run (FXCUP3_box) C++17
0 / 100
 3 ms 612 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 1<<19;
int n, a[maxn], b[maxn];

typedef pair<int, int> pint;
#define x first
#define y second

struct segt {
	pint t[maxn*2];
	pint merge(pint a, pint b) { return a.x > b.x ? a : b; }
	void update(int s, int e, int x, int p, int v) {
		if (s==e) t[x] = pint(v, p);
		else {
			int m = (s+e)/2;
			if (p<=m) update(s, m, 2*x, p, v);
			else update(m+1, e, 2*x+1, p, v);
			t[x] = merge(t[2*x], t[2*x+1]);
		}
	} void update(int p, int v) { update(0, maxn-1, 1, p, v); }
	pint query(int s, int e, int x, int l, int r) {
		if (l<=s and e<=r) return t[x];
		else if (l<=e and s<=r) {
			int m = (s+e)/2;
			return merge(query(s, m, 2*x, l, r), query(m+1, e, 2*x+1, l, r));
		} else return pint(-1, -1);
	} pint query(int l, int r) { return query(0, maxn-1, 1, l, r); }
} t;

void xfill(int s, int e, int l, int r) {
	if (s>e) return;
	int m = (s+e)/2, k = max(m, l);

	while (k+1<=r) {
		pint x = t.query(k-m+1, k);
		if (a[k+1] > x.x) break;
		k = x.y+m;
	}
	if (k>r) k = r;
	b[m] = k;

	if (s<e) {
		int m = (s+e)/2;
		xfill(s, m-1, l, k);
		xfill(m+1, e, k, r);
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);

	cin >> n;
	for (int i=1; i<=n; i++) cin >> a[i];
	for (int i=1; i<=n; i++) t.update(i, a[i]);

	xfill(1, n, 1, n);

	for (int i=1; i<=n; i++) {
		if (b[i] == n) cout << -1 << ' ';
		else cout << b[i] - i + 1 << ' ';
	}

}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Incorrect 3 ms 612 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 83.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 612 KB Output is correct
3 Correct 2 ms 612 KB Output is correct
4 Incorrect 3 ms 612 KB Output isn't correct
5 Halted 0 ms 0 KB -