Submission #1138694

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138694		Math4Life2020	Food Court (JOI21_foodcourt)	C++20	68 / 100	1097 ms	97264 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 262144; const ll E = 18; const ll INF = 1e18;

ll CLOCK=-1;
vector<pii> st1[2*Nm]; //lazy addition minus the lazy pushdowns
vector<ll> cvec; //vector of Cs
//{time, value}

ll st2[2*Nm]; //queue size segtree
ll lzadd[2*Nm]; //lazy add
ll lzmax[2*Nm]; //lazy max
//lazy max stores CURRENT true maximum to update to: aka incorporate add tag.
//value = max(value, lazy max tag)
//lazy tags have NOT been applied to the current element yet

inline ll v2(ll x) {
	return __builtin_ctz(x);
}

void upd1(ll l, ll r, ll k) {
	if (l>r) {
		return;
	}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		ll p = (1<<(E-vl))+(l>>vl);
		st1[p].push_back({CLOCK,st1[p].back().second+k});
		upd1(l+(1<<vl),r,k);
	} else {
		ll p = (1<<(E-vr))+(r>>vr);
		st1[p].push_back({CLOCK,st1[p].back().second+k});
		upd1(l,r-(1<<vr),k);
	}
}

void pdn(ll x) {
	if (x>=Nm) {
		st2[x]+=lzadd[x];
		st2[x]=max(st2[x],lzmax[x]);
		lzadd[x]=0;
		lzmax[x]=-INF;
		return;
	}
	if (lzadd[x]!=0) {
		lzadd[2*x]+=lzadd[x];
		lzmax[2*x]+=lzadd[x];
		lzadd[2*x+1]+=lzadd[x];
		lzmax[2*x+1]+=lzadd[x];
		st2[x]+=lzadd[x];
	}
	lzmax[2*x]=max(lzmax[2*x],lzmax[x]);
	lzmax[2*x+1]=max(lzmax[2*x+1],lzmax[x]);
	st2[x]=max(st2[x],lzmax[x]);
	lzadd[x]=0;
	lzmax[x]=-INF;
	return;
}

void aug2(ll l, ll r, ll k) {
	if (l>r) {
		return;
	}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		lzadd[(l>>vl)+(1<<(E-vl))]+=k;
		lzmax[(l>>vl)+(1<<(E-vl))]+=k;
		aug2(l+(1<<vl),r,k);
	} else {
		lzadd[(r>>vr)+(1<<(E-vr))]+=k;
		lzmax[(r>>vr)+(1<<(E-vr))]+=k;
		aug2(l,r-(1<<vr),k);
	}
}

void max2(ll l, ll r) {
	if (l>r) {
		return;
	}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		lzmax[(l>>vl)+(1<<(E-vl))]=max(0LL,lzmax[(l>>vl)+(1<<(E-vl))]);
		max2(l+(1<<vl),r);
	} else {
		lzmax[(r>>vr)+(1<<(E-vr))]=max(0LL,lzmax[(r>>vr)+(1<<(E-vr))]);
		max2(l,r-(1<<vr));
	}
}

void upd2(ll l, ll r, ll k) { //add k to range
	for (ll e=E;e>=0;e--) {
		pdn((l>>e)+(1<<(E-e)));
		pdn((r>>e)+(1<<(E-e)));
	}
	aug2(l,r,k);
}

void updM(ll l, ll r) {
	for (ll e=E;e>=0;e--) {
		pdn((l>>e)+(1<<(E-e)));
		pdn((r>>e)+(1<<(E-e)));
	}
	max2(l,r);
}

ll get2(ll x) {
	for (ll e=E;e>=0;e--) {
		pdn((x>>e)+(1<<(E-e)));
	}
	return st2[x+Nm];
}

ll get1(ll x, ll t=INF) {
	ll fv = 0;
	for (ll e=E;e>=0;e--) {
		ll p = (x>>e)+(1<<(E-e));
		if (t==INF) {
			fv += st1[p].back().second;
		} else {
			auto A0 = --lower_bound(st1[p].begin(),st1[p].end(),(pii){t,INF});
			fv += (*A0).second;
		}
	}
	return fv;
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	ll N,M,Q; cin >> N >> M >> Q;
	for (ll i=0;i<(2*Nm);i++) {
		lzmax[i]=-INF;
		st1[i].push_back({CLOCK,0});
	}
	vector<array<ll,5>> vupd;
	vector<pii> qdpt; //query depth (aka want ith element, store i), shop #
	for (ll q=0;q<Q;q++) {
		ll T; cin >> T;
		if (T==1) {
			ll L,R,C,K; cin >> L >> R >> C >> K;
			L--; R--;
			vupd.push_back({T,L,R,C,K});
			CLOCK++;
			upd1(L,R,K);
			cvec.push_back(C);
			upd2(L,R,K);
		} else if (T==2) {
			ll L,R,K; cin >> L >> R >> K;
			L--; R--;
			vupd.push_back({T,L,R,-1,K});
			upd2(L,R,-K);
			updM(L,R); 
		} else if (T==3) {
			ll A,B; cin >> A >> B;
			A--;
			ll nq = get2(A);
			//cout << "get1(A),get2(A)="<<get1(A)<<","<<get2(A)<<"\n";
			if (nq >= B) {
				qdpt.push_back({get1(A)-nq+B-1,A});
				//(get1(A)-nq)+(B-1)
			} else {
				qdpt.push_back({-1,-1});
			}
		}
	}
	for (pii p0: qdpt) {
		ll a = p0.second; ll d = p0.first;
		if (d==-1) {
			cout << "0\n"; continue;
		}
		ll tmin = -1;
		ll tmax = CLOCK+5;
		//binary search for the largest index of time for which
		//at most d elements currently in play
		//answer will be cvec[this time + 1]
		while (tmin<tmax) {
			ll t0 = (tmin+tmax+1)/2;
			if (get1(a,t0)<=d) {
				tmin = t0;
			} else {
				tmax = t0-1;
			}
		}
		cout << cvec[tmin+1]<<"\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