Submission #421861

#	Time	Username	Problem	Language	Result	Execution time	Memory
421861		shenxy	Food Court (JOI21_foodcourt)	C++11	100 / 100	665 ms	43664 KiB

foodcourt

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cassert>
#define m (s+e)/2
using namespace std;
typedef pair<int, int> ii;
int N, M, Q, T[250001], L[250001], R[250001], C[250001], ans[250001];
long long K[250001];
void readInt(int &x) {
	x = 0;
	char c = getchar_unlocked();
	while (c < '0' || c > '9') c = getchar_unlocked();
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c - '0');
		c = getchar_unlocked();
	}
}
void readLL(long long &x) {
	x = 0;
	char c = getchar_unlocked();
	while (c < '0' || c > '9') c = getchar_unlocked();
	while (c >= '0' && c <= '9') {
		x = (x << 3) + (x << 1) + (c - '0');
		c = getchar_unlocked();
	}
}
struct seg {
	int s, e;
	long long lazy, v;
	seg *l, *r;
	seg(int _s, int _e) {
		s = _s, e = _e;
		lazy = 0;
		v = 0;
		if (s != e) {
			l = new seg(s, m);
			r = new seg(m + 1, e);
		}
	}
	void prop() {
		if (lazy) {
			v += lazy;
			if (s != e) {
				l -> lazy += lazy;
				r -> lazy += lazy;
			}
			lazy = 0;
		}
	}
	void update(int a, int b, long long dv) {
		if (s != a || e != b) {
			if (a > m) r -> update(a, b, dv);
			else if (b <= m) l -> update(a, b, dv);
			else l -> update(a, m, dv), r -> update(m + 1, b, dv);
			l -> prop(), r -> prop();
			v = min(l -> v, r -> v);
		} else lazy += dv;
	}
	long long query(int a, int b) {
		prop();
		if (s == a && e == b) return v;
		if (a > m) return r -> query(a, b);
		if (b <= m) return l -> query(a, b);
		return min(l -> query(a, m), r -> query(m + 1, b));
	}
	int descend(int i, long long k) {
		prop();
		if (s == e) return s;
		if (m < i && r -> lazy + r -> v < k) return r -> descend(i, k);
		return l -> descend(i, k);
	}
} *r1;
struct Fenwick {
	long long ft[250001];
	Fenwick() {
		fill_n(ft, 250001, 0);
	}
	void update(int i, long long dv) {
		for (; i <= 250000; i += (i & -i)) ft[i] += dv;
	}
	long long query(int a) {
		long long ans = 0;
		for (; a > 0; a -= (a & -a)) ans += ft[a];
		return ans;
	}
	int descend(int i, long long k) {
		int ans = 0;
		for (int x = 17; x >= 0; --x) {
			if (ans + (1 << x) <= i && ft[ans + (1 << x)] < k) k -= ft[ans + (1 << x)], ans += 1 << x;
		}
		return ans;
	}
} r2;
int main() {
	readInt(N), readInt(M), readInt(Q);
	r1 = new seg(0, Q);
	ii ops[2 * Q];
	int ptr = 0;
	for (int i = 1; i <= Q; ++i) {
		readInt(T[i]);
		if (T[i] == 1) readInt(L[i]), readInt(R[i]), readInt(C[i]), readLL(K[i]);
		else if (T[i] == 2) readInt(L[i]), readInt(R[i]), readLL(K[i]);
		else readInt(L[i]), readLL(K[i]);
		ops[ptr++] = ii(L[i], i);
		if (R[i] != N && T[i] != 3) ops[ptr++] = ii(R[i] + 1, -i);
	}
	sort(ops, ops + ptr);
	for (int h = 0; h < ptr; ++h) {
		int i = ops[h].second;
		if (i < 0 && T[-i] == 1) r1 -> update(-i, Q, -K[-i]), r2.update(-i, -K[-i]);
		else if (i < 0 && T[-i] == 2) r1 -> update(-i, Q, K[-i]);
		else if (T[i] == 3) {
			long long curr = r1 -> query(i, i) - r1 -> query(0, i);
			int l = r2.descend(i, r2.query(i) - curr + K[i]);
			//printf("%d %lld %lld %d\n", i, r2.query(i), curr, l);
			if (l == i) ans[i] = 0;
			else ans[i] = C[l + 1];
		} else if (T[i] == 1) r1 -> update(i, Q, K[i]), r2.update(i, K[i]);
		else r1 -> update(i, Q, -K[i]);
		//for (int i = 0; i < Q; ++i) assert(r2.query(i) <= r2.query(i + 1));
	}
	for (int i = 1; i <= Q; ++i) {
		if (T[i] == 3) printf("%d\n", ans[i]);
	}
	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