Submission #1046574

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046574		GusterGoose27	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	28 / 100	240 ms	23316 KiB

mizuyokan2

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 25e4+5;
int Arr[MAXN];
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];
int tmx[2*MAXN];

void reset() {
	fill(tmx, tmx+2*n+2, -1);
}

void upd(int p, int v) {
	p += n+1;
	tmx[p] = max(tmx[p], v);
	for (p /= 2; p > 0; p /= 2) {
		tmx[p] = max(tmx[2*p], tmx[2*p+1]);
	}
}

int get_mx(int l, int r) {
	l += n+1;
	r += n+2;
	int ans = -1;
	for (; r > l; l /= 2, r /= 2) {
		if (l & 1) ans = max(ans, tmx[l++]);
		if (r & 1) ans = max(ans, tmx[--r]);
	}
	return ans;
}

typedef array<int, 2> ar2;

int solve() {
	reset();
	for (int i = 0; i < n; i++) to_activate[i].clear();
	pre[0] = 0;
	for (int i = 0; i < n; i++) pre[i+1] = pre[i] + arr[i];
	dp[n] = 0;
	to_activate[n-1].push_back(n);
	vector<int> fin_activate;
	for (int i = n-1; i >= 0; i--) {
		for (int v: to_activate[i]) {
			upd(v, dp[v]);
		}
		if (i == n-1) {
			dp[i] = 1;
		}
		else {
			if (sum(i+1, n-1) <= arr[i]) dp[i] = -1;
			else {
				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;
				}
				dp[i] = 2+get_mx(mx, n);
				assert(dp[i] >= 2);
			}
		}
		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;
			}
			if (mn == -1) fin_activate.push_back(i);
			else to_activate[mn].push_back(i);
		}
	}
	for (int v: fin_activate) {
		upd(v, dp[v]);
	}
	return max(dp[0], 1+get_mx(1, n));
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, q;
	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> Arr[i];
	}
	cin >> q;
	assert(q <= 10);
	while (q--) {
		int x, y, l, r;
		cin >> x >> y >> l >> r;
		Arr[x-1] = y;
		vector<int> cur;
		for (int i = l; i < r; i++) arr[i-l] = Arr[i];
		n = r-l;
		cout << solve() << '\n';
	}
}

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