Submission #70282136

---

Source Code Expand

#include <atcoder/all>
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
struct S {
	int x;
	int y;
};
S op(S c1, S c2) { return {c1.x + c2.x, c1.y + c2.y}; }
S e() { return {0, 0}; }
using F = int;
S mapping(F f, S c) {
	if (f == 0)
		c.x = 0;
	if (f == 1)
		c.x = c.y;
	return c;
}
F composition(F f, F g) { return f == -1 ? g : f; }
F id() { return -1; }
int x;
bool ga(S c) { return c.x <= x; }
int y;
bool gb(S c) { return c.x > y; }
int main() {
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int n;
	cin >> n;
	vector<int> w(n);
	for (int &i : w) cin >> i;
	vector<int> a(n);
	rep(i, n - 1) a[i + 1] = w[n - i - 1] - w[n - i - 2];
	vector<S> to_sega(n), to_segb(n);
	rep(i, n) {
		to_sega[i] = {0, a[i]};
		to_segb[i] = {-a[i], -a[i]};
	}
	atcoder::lazy_segtree<S, op, e, F, mapping, composition, id> seg_a(to_sega), seg_b(to_segb);
	int que;
	cin >> que;
	while (que--) {
		int ty;
		cin >> ty;
		if (ty == 1) {
			int v;
			cin >> v;
			v = n - v + 1;
			seg_a.apply(v, n, 0);
			seg_b.apply(v, n, 1);
			continue;
		}
		if (ty == 2) {
			int v;
			cin >> v;
			v = n - v + 1;
			seg_a.apply(v, n, 1);
			seg_b.apply(v, n, 0);
			continue;
		}
		cin >> x;
		y = x - w[n - 1];
		if (y >= 0) {
			cout << 0 << endl;
			continue;
		}
		cout << min(seg_a.max_right<ga>(0), seg_b.max_right<gb>(0)) << endl;
	}
}

Submission Info

Judge Result