Submission #465382

#	Time	Username	Problem	Language	Result	Execution time	Memory
465382		koioi.org-dennisstar	Food Court (JOI21_foodcourt)	C++17	100 / 100	622 ms	53008 KiB

foodcourt

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MX = 1<<19;

struct nd {
	ll v, mn;
	int i;
	nd() : v(0), mn(0), i(0) {}
}st[MX];

pair<ll, ll> pn[MX];

nd operator +(nd u, nd v) {
	nd r;
	r.v=u.v+v.v;
	if (pair<ll, int>(u.mn, u.i)<pair<ll, int>(u.v+v.mn, v.i)) r.mn=u.mn, r.i=u.i;
	else r.mn=u.v+v.mn, r.i=v.i;
	return r;
}

pair<ll, ll> operator +(pair<ll, ll> u, pair<ll, ll> v) {
	return {u.first+v.first, u.second+v.second};
}

void init(int i, int s, int e) {
	if (s==e) { st[i].i=-s; return ; }
	int m=(s+e)/2;
	init(i*2, s, m); init(i*2+1, m+1, e);
}

void upd(int i, int s, int e, int t, int v) {
	if (s==e) {
		st[i].v=v;
		st[i].mn=v;
		pn[i]={max(v, 0), min(v, 0)};
		return ;
	}
	int m=(s+e)/2;
	if (t<=m) upd(i*2, s, m, t, v);
	else upd(i*2+1, m+1, e, t, v);
	st[i]=st[i*2]+st[i*2+1];
	pn[i]=pn[i*2]+pn[i*2+1];
}

nd get(int i, int s, int e, int t) {
	if (t<s) return nd();
	if (e<=t) return st[i];
	int m=(s+e)/2;
	return get(i*2, s, m, t)+get(i*2+1, m+1, e, t);
}

pair<ll, ll> get(int i, int s, int e, int l, int r) {
	if (e<l||r<s||r<l) return {0, 0};
	if (l<=s&&e<=r) return pn[i];
	int m=(s+e)/2;
	return get(i*2, s, m, l, r)+get(i*2+1, m+1, e, l, r);
}

int srh(int i, int s, int e, ll v) {
	if (s==e) {
		if (pn[i].first>=v) return s;
		return s+1;
	}
	int m=(s+e)/2;
	if (pn[i*2].first>=v) return srh(i*2, s, m, v);
	else return srh(i*2+1, m+1, e, v-pn[i*2].first);
}

int main() {
	cin.tie(0)->sync_with_stdio(0);

	int n, m, q;
	cin>>n>>m>>q;
	
	vector<int> ty(q+1);
	vector<vector<pair<int, ll>>> ch(n+2), ask(n+1);
	vector<pair<int, int>> ans;
	
	for (int i=1; i<=q; i++) {
		int qu;
		cin>>qu;
		if (qu==1) {
			int l, r, k;
			cin>>l>>r>>ty[i]>>k;
			ch[l].emplace_back(i, k);
			ch[r+1].emplace_back(i, 0);
		}
		if (qu==2) {
			int l, r, k;
			cin>>l>>r>>k;
			ch[l].emplace_back(i, -k);
			ch[r+1].emplace_back(i, 0);
		}
		if (qu==3) {
			int a; ll b;
			cin>>a>>b;
			ask[a].emplace_back(i, b);
		}
	}

	init(1, 0, q);
	for (int i=1; i<=n; i++) {
		for (auto &j:ch[i]) upd(1, 0, q, j.first, j.second);
		for (auto &j:ask[i]) {
			int mi=-get(1, 0, q, j.first).i;
			int ai=srh(1, 0, q, get(1, 0, q, 0, mi).first-get(1, 0, q, mi+1, j.first).second+j.second);
			ans.emplace_back(j.first, ai>j.first?0:ty[ai]);
		}
	}
	
	sort(ans.begin(), ans.end());
	for (auto &i:ans) cout<<i.second<<'\n';

	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