Submission #474074

#	Time	Username	Problem	Language	Result	Execution time	Memory
474074		grt	Food Court (JOI21_foodcourt)	C++17	100 / 100	516 ms	49888 KiB

foodcourt

#include <bits/stdc++.h>
#define PB push_back
#define ST first
#define ND second

//#pragma GCC optimize ("O3")
//#pragma GCC target("tune=native")

//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
//using namespace __gnu_pbds;
//typedef tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

using namespace std;
using ll = long long;
using pi = pair<int, int>;
using vi = vector<int>;

struct Node {
	ll f, g, ignore;
};

const int nax = 250 * 1000 + 10;
const ll INF = 1e18;
int n, m, q;
Node T[(1<<19)];
ll T2[(1<<19)];
vi ids[nax];
int R;

void prop(int v) {
	T[2*v].f = max(T[2*v].f, T[v].f - T[2*v].g);
	T[2*v+1].f = max(T[2*v+1].f, T[v].f - T[2*v+1].g);
	T[2*v].g += T[v].g;
	T[2*v+1].g += T[v].g;
	T[2*v].ignore += T[v].ignore;
	T[2*v+1].ignore += T[v].ignore;
	T[v].ignore = 0;
	T[v].g = 0;
	T[v].f = -INF;
}

void add(int a, ll x) {
	a += R;
	T2[a] += x;
	while(a > 1) {
		a /= 2;
		T2[a] += x;
	}
}

void upd(int a, int b, ll x, int l, int r, int v) {
	if(a <= l && r <= b) {
		T[v].g += x;
		if(x > 0) {
			T[v].ignore += x;
		}
		T[v].f = max(T[v].f, -T[v].g);
		return;
	}
	prop(v);
	int mid = (l + r) / 2;
	if(a <= mid) upd(a,b,x,l,mid,v*2);
	if(mid < b) upd(a,b,x,mid+1,r,v*2+1);
}

pair<ll,ll> qr(int a, int l, int r, int v) {
	if(l == r) {
		return make_pair(T[v].f + T[v].g, T[v].ignore);
	}
	prop(v);
	int mid = (l + r) / 2;
	if(a <= mid) return qr(a, l, mid, v * 2);
	else return qr(a, mid + 1, r, v * 2 + 1);
}

void init(int l, int r, int v) {
	T[v].f = T[v].g = T[v].ignore = 0;
	if(l == r) {
		return;
	}
	int mid = (l + r) / 2;
	init(l,mid,v*2);
	init(mid+1,r,v*2+1);
}

int fp(ll x) {
	int v = 1;
	while(v < R) {
		if(T2[2*v] >= x) {
			v = v * 2;
		} else {
			x -= T2[2*v];
			v = v * 2 + 1;
		}
	}
	return v - R;
}

ll absOrd[nax];
vi events[nax];
int ans[nax];
pair<ll,int>delta[nax];
vi qrs;

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	for(int i = 1; i <= q; ++i) {
		int type;
		cin >> type;
		if(type == 1) {
			int l,r,c;
			ll k;
			cin >> l >> r >> c >> k;
			upd(l, r, k, 1, n, 1);
			events[l].PB(i);
			events[r + 1].PB(-i);
			delta[i] = {k, c};
		} else if(type == 2) {
			int l,r;
			ll k;
			cin >> l >> r >> k;
			upd(l, r, -k, 1, n, 1);
		} else {
			int a;
			ll b;
			cin >> a >> b;
			qrs.PB(i);
			auto [x, y] = qr(a, 1, n, 1);
			if(x < b) {
				ans[i] = 0;
			} else {
				ids[a].PB(i);
				absOrd[i] = y - (x - b);
			}
		}
	}
	R = 1;
	while(R <= q) {
		R *= 2;
	}
	for(int i = 1; i <= n; ++i) {
		for(int id : events[i]) {
			if(id > 0) {
				add(id, delta[id].ST);
			} else {
				add(-id, -delta[-id].ST);
			}
		}
		for(int id : ids[i]) {
			ans[id] = delta[fp(absOrd[id])].ND;
		}
	}
	for(int x : qrs) {
		cout << ans[x] << "\n";
	}
}

• 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