oj.uz

답안 #72094

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
72094 2018-08-26T05:15:23 Z @younha_holic(#2227, jun6873, rkm0959) 박스런 (FXCUP3_box) C++17
17 / 100
 1000 ms 8556 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++;
	}
	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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -