Submission #72094

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
72094	2018-08-26T05:15:23 Z	@younha_holic(#2227, jun6873, rkm0959)	Box Run (FXCUP3_box)	C++17	17 / 100	1000 ms	8556 KB

box

#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++;
	}
	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

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	3 ms	484 KB	Output is correct
4	Correct	2 ms	548 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	4 ms	668 KB	Output is correct
7	Correct	3 ms	668 KB	Output is correct
8	Correct	2 ms	668 KB	Output is correct
9	Correct	3 ms	668 KB	Output is correct
10	Correct	3 ms	668 KB	Output is correct
11	Correct	3 ms	668 KB	Output is correct

Subtask #2

0 / 83.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	380 KB	Output is correct
2	Correct	2 ms	484 KB	Output is correct
3	Correct	3 ms	484 KB	Output is correct
4	Correct	2 ms	548 KB	Output is correct
5	Correct	3 ms	624 KB	Output is correct
6	Correct	4 ms	668 KB	Output is correct
7	Correct	3 ms	668 KB	Output is correct
8	Correct	2 ms	668 KB	Output is correct
9	Correct	3 ms	668 KB	Output is correct
10	Correct	3 ms	668 KB	Output is correct
11	Correct	3 ms	668 KB	Output is correct
12	Correct	5 ms	704 KB	Output is correct
13	Correct	14 ms	748 KB	Output is correct
14	Correct	136 ms	2048 KB	Output is correct
15	Correct	244 ms	2904 KB	Output is correct
16	Correct	367 ms	3660 KB	Output is correct
17	Correct	973 ms	8240 KB	Output is correct
18	Execution timed out	1050 ms	8556 KB	Time limit exceeded
19	Halted	0 ms	0 KB	-