Submission #670927

#	Time	Username	Problem	Language	Result	Execution time	Memory
670927		Kahou	Food Court (JOI21_foodcourt)	C++14	13 / 100	1092 ms	132160 KiB

foodcourt

/* In the name of God, aka Allah */
// let this be mytemp.cpp
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define endl '\n'
#define mk make_pair
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int N = 2.5e5 + 50;
ll n, m, q, out[N];
vector<pll> qr[N];
vector<pll> bd[N<<2];
vector<pair<ll, pll>> vc[N<<2];
pll fen[N];

void join(ll l, ll r, ll c, ll k, ll tim, ll u=1, ll tl=1, ll tr=n) {
	if (r < tl || tr < l) return;
	if (l <= tl && tr <= r) {
		vc[u].push_back({tim, {k, c}});
		return;
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	join(l, r, c, k, tim, lc, tl, md), join(l, r, c, k, tim, rc, md+1, tr);
}
void leave(ll l, ll r, ll k, ll tim, ll u=1, ll tl=1, ll tr=n) {
	if (r < tl || tr < l) return;
	if (l <= tl && tr <= r) {
		bd[u].push_back({tim, k});
		return;
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	leave(l, r, k, tim, lc, tl, md), leave(l, r, k, tim, rc, md+1, tr);
}
void service(ll id, ll x, ll tim, ll u=1, ll tl=1, ll tr=n) {
	if (id < tl || tr < id) return;
	if (tl == tr) {
		qr[tl].push_back({tim, x});
		return;
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	service(id, x, tim, lc, tl, md), service(id, x, tim, rc, md+1, tr);
}

void upd(ll i, ll x) {
	if (!i) return fen[i].F += x, void();
	for (; i < N; i += i&-i) {
		fen[i].F += x;
	}
}
ll get(ll x) {
	ll id = 0;
	x -= fen[0].F;
	for (ll k = 18; k >= 0; k--) {
		if (id+(1<<k) < N && fen[id^(1<<k)].F < x) {
			id ^= (1<<k);
			x -= fen[id].F;
		}
	}
	id++;
	return id;
}

void dfs(ll u=1, ll tl=1, ll tr=n) {
	for (pll x: bd[u]) {
		upd(0, x.S);
	}
	for (pair<ll, pll> x:vc[u]) {
		fen[x.F].S = x.S.S;
		upd(x.F, x.S.F);
	}
	if (tl == tr) {
		for (pll x:qr[tl]) {
			ll id = get(x.S);
			cerr << "OK " << x.F << ' ' << x.S << ' ' << id << endl;
			out[x.F] = (id < x.F? fen[id].S : 0);
		}
	}
	ll md = (tl+tr)/2;
	ll lc = u<<1;
	ll rc = u<<1|1;
	if (tl < tr) dfs(lc, tl, md), dfs(rc, md+1, tr);

	for (pair<ll, pll> x:vc[u]) {
		fen[x.F].S = 0;
		upd(x.F, -x.S.F);
	}
	reverse(bd[u].begin(), bd[u].end());
	for (pll x: bd[u]) {
		upd(0, x.S);
	}
}

void solve() {
	cin >> n >> m >> q;
	for (ll i = 1; i <= q; i++) {
		out[i] = -1;
		ll t, l, r, k, c, id, x;
		cin >> t;
		if (t == 1) {
			cin >> l >> r >> c >> k;
			join(l, r, c, k, i);
		}
		if (t == 2) {
			cin >> l >> r >> k;
			leave(l, r, k, i);
		}
		if (t == 3) {
			cin >> id >> x;
			service(id, x, i);
		}
	}
	dfs();
	for (ll i = 1; i <= q; i++) {
		if (out[i] < 0) continue;
		cout << out[i] << endl;
	}
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	solve();
	return 0;
}

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