Submission #645395

#	Time	Username	Problem	Language	Result	Execution time	Memory
645395		GusterGoose27	Food Court (JOI21_foodcourt)	C++11	68 / 100	1095 ms	302236 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

class ptree {
public:
	int lp, rp;
	ptree *l = nullptr;
	ptree *r = nullptr;
	ll s = 0;
	ptree(int lv, int rv) {
		lp = lv;
		rp = rv;
		if (lp != rp) {
			int mid = (lp+rp)/2;
			l = new ptree(lp, mid);
			r = new ptree(mid+1, rp);
		}
	}
	ptree(ptree *t, int lupd = 0) {
		lp = t->lp;
		rp = t->rp;
		l = t->l;
		r = t->r;
		s = t->s+lupd;
	}
	ptree(ptree *lt, ptree *rt, ll curs) {
		l = lt;
		r = rt;
		lp = l->lp;
		rp = r->rp;
		s = curs;
	}
	ptree *upd(int lv, int rv, int v) {
		if (lp > rv || rp < lv) return this;
		if (lp >= lv && rp <= rv) {
			return new ptree(this, v);
		}
		return new ptree(l->upd(lv, rv, v), r->upd(lv, rv, v), s);
	}
	ll query(int p) {
		if (lp == rp) return s;
		if (p > (lp+rp)/2) return s+r->query(p);
		return s+l->query(p);
	}
};

const int MAX_ALLOC = 524288;
int sz;

class stree {
public:
	pii lz[MAX_ALLOC];
	stree() {
		fill(lz, lz+(int)pow(2, ceil(log2(sz))), pii(0, 0));
	}
	void merge(int cur, pii p) {
		lz[cur].first += p.first;
		lz[cur].second += p.first;
		lz[cur].second = max(lz[cur].second, p.second);
	}
	void prop(int cur) {
		merge(2*cur, lz[cur]);
		merge(2*cur+1, lz[cur]);
		lz[cur] = pii(0, 0);
	}
	void upd(int lv, int rv, int v, int cur = 1, int lp = 0, int rp = sz-1) {
		if (lp > rv || rp < lv) return;
		if (lp >= lv && rp <= rv) {
			merge(cur, pii(v, 0));
			return;
		}
		prop(cur);
		int mid = (lp+rp)/2;
		upd(lv, rv, v, 2*cur, lp, mid);
		upd(lv, rv, v, 2*cur+1, mid+1, rp);
	}
	ll getv(int p, int cur = 1, int lp = 0, int rp = sz-1) {
		if (lp == rp) return max(lz[cur].first, lz[cur].second);
		prop(cur);
		int mid = (lp+rp)/2;
		if (p <= mid) return getv(p, 2*cur, lp, mid);
		else return getv(p, 2*cur+1, mid+1, rp);
	}
};

const int MAXN = 250000;
int n, m, q;
int upd_id[MAXN];
ptree *trees[MAXN];
stree *net_tree;
int ev_num = 0;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n >> m >> q;
	ptree *cur_tree = new ptree(0, n-1);
	sz = n;
	stree *net_tree = new stree();
	for (int i = 0; i < q; i++) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r, c, k; cin >> l >> r >> c >> k;
			l--; r--;
			upd_id[ev_num] = c;
			cur_tree = cur_tree->upd(l, r, k);
			trees[ev_num] = cur_tree;
			net_tree->upd(l, r, k);
			ev_num++;
		}
		if (t == 2) {
			int l, r, k; cin >> l >> r >> k;
			l--; r--;
			net_tree->upd(l, r, -k);
		}
		if (t == 3) {
			int a; ll b; cin >> a >> b; a--;
			ll cur_sz = net_tree->getv(a);
			if (cur_sz < b) {
				cout << "0\n";
				continue;
			}
			ll num_adds = trees[ev_num-1]->query(a);
			ll req_sz = num_adds-cur_sz+b;
			int mn = -1;
			int mx = ev_num-1;
			while (mx > mn+1) {
				int cur = (mn+mx)/2;
				if (trees[cur]->query(a) < req_sz) mn = cur;
				else mx = cur;
			}
			cout << upd_id[mx] << "\n";
		}
	}
}

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