Submission #1046600

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046600		GusterGoose27	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	0 / 100	79 ms	53496 KiB

mizuyokan2

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 25e4+5;
const int MAXB = 18;
int arr[MAXN];
typedef long long ll;
ll pre[MAXN];
int n;

ll sum(int l, int r) {
	return pre[r+1] - pre[l];
}

int dp[MAXN];
vector<int> to_activate[MAXN];

typedef array<int, 2> ar2;
ar2 nxt[MAXN][MAXB];
int spos[MAXN];

ll vpre(int v) {
	return arr[v] + pre[v+1];
}

int lift(int l, int r, int cur = -1) {
	if (cur == -1) return max(lift(l, r, l), 1+lift(l, r, spos[l]));
	if (cur >= r) return -1;
	for (int i = MAXB-1; i >= 0; i--) {
		if (nxt[cur][i][0] < r) return lift(l, r, nxt[cur][i][0]) + nxt[cur][i][1];
	}
	if (sum(cur+1, r-1) > arr[cur]) return 2;
	return 1;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n, q;
	cin >> n;
	pre[0] = 0;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		pre[i+1] = pre[i] + arr[i];
	}
	// implement a mon stack to keep track of next smaller. we want to track value + prefix
	vector<int> stck;
	set<int> active;
	// to_activate[n-1].push_back(n);
	active.insert(n);
	nxt[n][0] = {n, 0};
	for (int i = n-1; i >= 0; i--) {
		nxt[i][0] = {n, 0};
		while (!stck.empty() && vpre(i) <= vpre(stck.back())) stck.pop_back();
		if (stck.empty()) {
			if (sum(i+1, n-1) > arr[i]) {
				int mn = i+1, mx = n;
				while (mx > mn+1) {
					int mid = (mn+mx)/2;
					if (sum(i+1, mid-1) > arr[i]) mx = mid;
					else mn = mid;
				}
				nxt[i][0] = {*active.lower_bound(mx), 2};
			}
		}
		else {
			nxt[i][0] = {stck.back(), 0};
		}
		stck.push_back(i);
		if (sum(0, i-1) > arr[i]) {
			int mn = -1;
			int mx = i-1;
			while (mx > mn+1) {
				int mid = (mn+mx)/2;
				if (sum(mid+1, i-1) > arr[i]) mn = mid;
				else mx = mid;
			}
			to_activate[mx].push_back(i);
		}
		for (int v: to_activate[i]) {
			active.insert(v);
		}
		spos[i] = *active.begin();
	}
	for (int j = 1; j < MAXB; j++) {
		for (int i = 0; i <= n; i++) {
			nxt[i][j] = {nxt[nxt[i][j-1][0]][j-1][0], nxt[i][j-1][1] + nxt[nxt[i][j-1][0]][j-1][1]};
		}
	}
	cin >> q;
	while (q--) {
		int x, y, l, r;
		cin >> x >> y >> l >> r;
		assert(arr[x-1] == y);
		cout << lift(l, r) << '\n';
	}
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11