Submission #72085

#	Time	Username	Problem	Language	Result	Execution time	Memory
72085		@younha_holic (#118)	Box Run (FXCUP3_box)	C++17	0 / 100	3 ms	612 KiB

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 = 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
• Subtask 2: 0 / 83