Submission #684588

#	Time	Username	Problem	Language	Result	Execution time	Memory
684588		NK_	Food Court (JOI21_foodcourt)	C++17	100 / 100	450 ms	53976 KiB

foodcourt

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;

#define nl '\n'

using ll = long long;

using T = array<ll, 2>;

struct Seg {
	vector<ll> suf, pos, all; int N;

	void init(int n) {
		N = 1; while(N < n) N *= 2; 
		suf.assign(2*N, 0); pos.assign(2*N, 0); all.assign(2*N, 0);
	}

	void pull(int p) {
		pos[p] = pos[2*p] + pos[2*p+1];
		all[p] = all[2*p] + all[2*p+1];
		suf[p] = max(suf[2*p] + all[2*p+1], suf[2*p+1]);
	}

	void upd(int p, ll v, int x, int L, int R) {
		if (p < L || R < p) return;
		if (L == R) {
			suf[x] = all[x] = v;
			pos[x] = max(v, 0LL);
			return;
		}

		int M = (L+R)/2;
		upd(p, v, 2*x, L, M); upd(p, v, 2*x+1, M+1, R);
		pull(x);
	}

	T max_suf(int l, int r, int x, int L, int R) {
		if (r < L || R < l) return T{0, 0};
		if (l <= L && R <= r) return T{suf[x], all[x]};

		int M = (L+R)/2;
		T a = max_suf(l, r, 2*x, L, M), b = max_suf(l, r, 2*x+1, M+1, R);

		return {max(a[0] + b[1], b[0]), a[1] + b[1]};
	};

	ll sum_pos(int l, int r, int x, int L, int R) {
		if (r < L || R < l) return 0;
		if (l <= L && R <= r) return pos[x];
		int M = (L+R)/2;
		return sum_pos(l, r, 2*x, L, M) + sum_pos(l, r, 2*x+1, M+1, R);
	}

	int walk(int l, int r, ll v, ll V, int x, int L, int R) {
		// cout << x << " " << L << " " << R << " " << V << endl;
		// cout << l << " " << r << " " << v << endl;
		if (r < L || R < l || v > V) return -1;
		if (L == R) return L;

		int M = (L+R)/2;

		int res = walk(l, r, v, V - pos[2*x+1], 2*x, L, M);
		if (res == -1) return walk(l, r, v, V, 2*x+1, M+1, R);
		return res;
	}

	void upd(int p, int x) { upd(p, x, 1, 0, N-1); }
	T max_suf(int l, int r) { return max_suf(l, r, 1, 0, N-1); }
	ll sum_pos(int l, int r) { return sum_pos(l, r, 1, 0, N-1); }
	ll walk(int l, int r, ll v) { return walk(l, r, v, pos[1], 1, 0, N-1); }
};



int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N, M, Q; cin >> N >> M >> Q;

	vector<vector<int>> QL(N), QR(N), QQ(N);

	vector<ll> C(Q), K(Q);

	for(int q = 0; q < Q; q++) {
		int t; cin >> t;
		if (t == 1) {
			int l, r; cin >> l >> r >> C[q] >> K[q]; --l, --r;
			QL[l].push_back(q);
			QR[r].push_back(q);
		}

		if (t == 2) {
			int l, r; cin >> l >> r >> K[q]; --l, --r;
			K[q] = -K[q], C[q] = -1;
			QL[l].push_back(q);
			QR[r].push_back(q);
		}

		if (t == 3) {
			int i; cin >> i >> K[q]; --i;
			QQ[i].push_back(q);
		}
	}

	Seg st; st.init(Q);

	vector<ll> ans(Q, -1);

	for(int i = 0; i < N; i++) {
		for(auto q : QL[i]) { st.upd(q, K[q]);/* cout << "ON: " << q << endl;*/ }

		for(auto q : QQ[i]) {
			ll pos = st.sum_pos(0, q), suf = st.max_suf(0, q)[0];

			ll I = pos - suf + K[q];
			// cout << "INFO: " << q << " " << pos << " " << suf << " " << I << endl;

			int res = st.walk(0, q, I);
			assert(res == -1 || res <= q);
			ans[q] = (res == -1 ? 0 : C[res]);
			// cout << "DONE: " << res << endl;
		}

		for(auto q : QR[i]) { st.upd(q, 0); /*cout << "OFF: " << q << endl;*/ }
	}

	for(int q = 0; q < Q; q++) if (ans[q] != -1) cout << ans[q] << nl;

    return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 7 / 7
• Subtask 4: 21 / 21
• Subtask 5: 15 / 15
• Subtask 6: 13 / 13
• Subtask 7: 26 / 26
• Subtask 8: 11 / 11