Submission #426128

#	Time	Username	Problem	Language	Result	Execution time	Memory
426128		8e7	Food Court (JOI21_foodcourt)	C++14	100 / 100	982 ms	59712 KiB

foodcourt

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b){ cout << a << " ";debug(b ...);};
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 250005
#define pii pair<ll, ll>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
//using namespace __gnu_pbds;

struct segtree{
	ll seg[4 * maxn], tag[4 * maxn], sum[4 * maxn];
	void modify(int cur, int l, int r, int ql, int qr, ll val) {
		if (r <= l || qr <= l || ql >= r) return;
		if (ql <= l && qr >= r) {
			tag[cur] += val;
			return;
		}
		int mid = (l + r) / 2;
		modify(cur * 2, l, mid, ql, qr, val);
		modify(cur * 2 + 1, mid, r, ql, qr, val);
		seg[cur] = min(seg[cur * 2] + tag[cur * 2], seg[cur * 2 + 1] + tag[cur * 2 + 1]);
		sum[cur] = sum[cur * 2] + tag[cur * 2] * (mid - l) + sum[cur * 2 + 1] + tag[cur * 2 + 1] * (r - mid);
	}
	ll query(int cur, int l, int r, int ql, int qr) {
		if (r <= l || qr <= l || ql >= r) return 1LL<<60;
		if (ql <= l && qr >= r) return seg[cur] + tag[cur];
		int mid = (l + r) / 2;
		return tag[cur] + min(query(cur * 2, l, mid, ql, qr), query(cur * 2 + 1, mid, r, ql, qr));	
	}
	int search(int cur, int l, int r, ll val) { //leftmost index with sum >= val
		//debug(l, r, sum[cur], val);
		if (r <= l) return 0;
		if (r - l == 1) return l;
		int mid = (l + r) / 2;
		if (sum[cur * 2] + (tag[cur * 2] + tag[cur]) * (mid - l) >= val) {
			return search(cur * 2, l, mid, val - tag[cur] * (mid - l));
		} else {
			return search(cur * 2 + 1, mid, r, val - sum[cur * 2] - tag[cur * 2] * (mid - l) - tag[cur] * (r - l));
		}
	}
	ll getsum(int cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return 0;
		if (ql <= l && qr >= r) return sum[cur] + tag[cur] * (r - l);
		int mid = (l + r) / 2;
		return getsum(cur * 2, l, mid, ql, qr) + getsum(cur * 2 + 1, mid, r, ql, qr) + tag[cur] * (min(r, qr) - max(l, ql));
	}
} se, bst;
vector<pii> query[maxn], mod[maxn], arr[maxn]; 
int col[maxn];
ll ans[maxn];
int main() {
	io
	int n, m, q;
	cin >> n >> m >> q;
	vector<int> qind;
	for (int i = 0;i < q;i++) {
		int type;
		cin >> type;
		if (type == 1) {
			ll l, r, c, k;
			cin >> l >> r >> c >> k;
			col[i] = c;
			arr[l].push_back({i, k});
			arr[r + 1].push_back({i, -k});
			mod[l].push_back({i, k});
			mod[r + 1].push_back({i, -k});
		} else if (type == 2) {
			ll l, r, k;
			cin >> l >> r >> k;
			mod[l].push_back({i, -k});
			mod[r + 1].push_back({i, k});
		} else {
			ll ind, num;
			cin >> ind >> num;
			query[ind].push_back({i, num});
			qind.push_back(i);
		}
	}
	for (int i = 1;i <= n;i++) {
		for (auto j:mod[i]) {
			se.modify(1, 0, q, j.ff, q, j.ss);			
		}
		for (auto j:arr[i]) {
			bst.modify(1, 0, q, j.ff, j.ff + 1, j.ss);
		}
		for (auto j:query[i]) {
			ll val = min(0LL, se.query(1, 0, q, 0, j.ff + 1));
			ll pnt = se.query(1, 0, q, j.ff, j.ff + 1);
			//debug(i, j.ss, pnt, val);
			if (pnt - val >= j.ss) {
				ll rem = bst.getsum(1, 0, q, 0, j.ff + 1) - (pnt - val);
				j.ss += rem;
				//debug(i, j.ss, bst.search(1, 0, q, j.ss));
				ans[j.ff] = col[bst.search(1, 0, q, j.ss)];
				//ans[j.ff] = 1;
			} else {
				ans[j.ff] = 0;
			}
		}
	}
	for (int i:qind) {
		cout << ans[i] << "\n";
	}
}
/*
5 5 9
1 2 3 5 2
1 1 2 2 4
3 2 3
1 1 2 2 4
3 2 5
1 3 4 1 3
3 4 1 
3 5 4
3 3 4

4 1 7
1 1 3 1 5
1 2 4 1 3
2 1 3 5 
1 3 4 1 7
3 3 4
3 2 3
3 1 1
   */

• 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