Submission #1104957

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104957		penguinhacker	Food Court (JOI21_foodcourt)	C++17	68 / 100	1066 ms	41548 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ar array

const int mxN=250000;
int n, m, q, qs[mxN], ans[mxN];
ar<ll, 3> st[1<<19]; // sum, suf, sum of negs
vector<ar<int, 2>> changes[mxN];
vector<ar<ll, 2>> qq[mxN];

ar<ll, 3> cmb(ar<ll, 3> a, ar<ll, 3> b) {
	return {a[0]+b[0], max(a[1]+b[0], b[1]), a[2]+b[2]};
}

void upd(int i, int x, int u=1, int l=0, int r=q-1) {
	if (l==r) {
		st[u][0]+=x;
		st[u][1]=max(st[u][0], 0ll);
		st[u][2]=min(st[u][0], 0ll);
		return;
	}
	int mid=(l+r)/2;
	if (i<=mid)
		upd(i, x, 2*u, l, mid);
	else
		upd(i, x, 2*u+1, mid+1, r);
	st[u]=cmb(st[2*u], st[2*u+1]);
}

ar<ll, 3> qry1(int ql, int qr, int u=1, int l=0, int r=q-1) {
	if (l>qr||r<ql)
		return {};
	if (ql<=l&&r<=qr)
		return st[u];
	int mid=(l+r)/2;
	return cmb(qry1(ql, qr, 2*u, l, mid), qry1(ql, qr, 2*u+1, mid+1, r));
}

ar<ll, 2> qry2(int ql, ll k, int u=1, int l=0, int r=q-1) {
	if (r<ql)
		return {-1, 0};
	if (ql<=l&&st[u][2]<k)
		return {-1, st[u][0]};
	if (l==r)
		return {l, 0};
	int mid=(l+r)/2;
	ar<ll, 2> x=qry2(k, 2*u, l, mid);
	if (x[0]!=-1)
		return x;
	return qry2(k-x[1], 2*u+1, mid+1, r);
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> q;
	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;
			qs[i]=c;
			changes[l].push_back({i, k});
			if (r+1<n)
				changes[r+1].push_back({i, -k});
		} else if (t==2) {
			int l, r, k;
			cin >> l >> r >> k, --l, --r;
			changes[l].push_back({i, -k});
			if (r+1<n)
				changes[r+1].push_back({i, k});
		} else {
			int a;
			ll b;
			cin >> a >> b, --a;
			qq[a].push_back({i, b});
		}
		ans[i]=-1;
	}
	for (int i=0; i<n; ++i) {
		for (auto [t, k] : changes[i])
			upd(t, k);
		for (auto [ind, k] : qq[i]) {
			ar<ll, 3> x=qry1(0, ind);
			if (x[1]<k) {
				ans[ind]=0;
				continue;
			}
			int lb=0, rb=ind;
			while(lb<rb) {
				int mid=(lb+rb+1)/2;
				if (qry1(mid, ind)[1]==x[1])
					lb=mid;
				else
					rb=mid-1;
			}
			ll neg=qry1(lb, ind)[2];
			int s=lb;
			rb=ind;
			while(lb<rb) {
				int mid=(lb+rb)/2;
				ar<ll, 3> y=qry1(s, mid);
				if (y[0]-y[2]+neg>=k)
					rb=mid;
				else
					lb=mid+1;
			}
			ans[ind]=qs[lb];
		}
	}
	for (int i=0; i<q; ++i)
		if (~ans[i])
			cout << ans[i] << "\n";
	return 0;
}

• 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