Submission #1138952

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138952		Math4Life2020	Food Court (JOI21_foodcourt)	C++20	100 / 100	312 ms	47548 KiB

foodcourt

//#pragma GCC optimize("O3,unroll-loops")
#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 ans[Nm]; //query answer

ll st1[2*Nm]; //lazy addition minus the lazy pushdowns

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

pii st3[2*Nm]; //{min value, x location}
ll lz3[2*Nm]; //lazy add
//lazy tags HAVE been applied to the current element
vector<pii> vqry[Nm]; //{query value, query index}
ll qind[Nm];
//for query value: store how much query value exceeds previous query value

pii fz(pii p1, pii p2) {
	if (p1.first>p2.first) {
		return p2;
	} 
	if (p1.first<p2.first) {
		return p1;
	}
	if (p1.second>p2.second) {
		return p2;
	} else {
		return p1;
	}
}

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]=st1[p]+k;
		upd1(l+(1<<vl),r,k);
	} else {
		ll p = (1<<(E-vr))+(r>>vr);
		st1[p]=st1[p]+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];
		lzadd[x]=0;
	}
	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]);
	lzmax[x]=-INF;
}

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 get1INF(ll x) {
	ll fv = 0;
	for (ll e=(E-1);e>=0;e--) {
		ll p = (x>>e)+(1<<(E-e));
		fv += st1[p];
	}
	return fv;
}

void pdn3(ll x) {
	if (x>=Nm) {
		lz3[x]=0;
		return;
	}
	st3[2*x].first+=lz3[x];
	lz3[2*x]+=lz3[x];
	st3[2*x+1].first+=lz3[x];
	lz3[2*x+1]+=lz3[x];
	lz3[x]=0;
}

void lft3(ll x) {
	if (x<Nm && lz3[x]==0) {
		st3[x]=fz(st3[2*x],st3[2*x+1]);
	}
}

void stinc(ll x, ll k, ll c) {
	// cout << "stinc: x,k,c="<<x<<","<<k<<","<<c<<"\n";
	st3[x].first-=k;
	lz3[x]-=k;
	// cout << "st3[x].first="<<st3[x].first<<"\n";
	// cout << "st3[x].second="<<st3[x].second<<"\n";
	//return;
	while(st3[x].first<0) {
		ll y = st3[x].second;
		for (ll e=E;e>=0;e--) {
			pdn3((y>>e)+(1<<(E-e)));
		}
		ans[vqry[y][qind[y]].second]=c;
		qind[y]++;
		if (vqry[y].size()<=qind[y]) {
			st3[y+Nm]={INF,INF};
		} else {
			st3[y+Nm]={st3[y+Nm].first+vqry[y][qind[y]].first,y};
		}
		for (ll e=0;e<=E;e++) {
			lft3((y>>e)+(1<<(E-e)));
		}
		// cout << "st3[x].first="<<st3[x].first<<"\n";
		// cout << "st3[x].second="<<st3[x].second<<"\n";
		// return;
	} 
}

void aug3(ll l, ll r, ll k, ll c) {
	if (l>r) {
		return;
	}
	ll vl = v2(l); ll vr = v2(r+1);
	if (vl<vr) {
		stinc((l>>vl)+(1<<(E-vl)),k,c);
		aug3(l+(1<<vl),r,k,c);
	} else {
		stinc((r>>vr)+(1<<(E-vr)),k,c);
		aug3(l,r-(1<<vr),k,c);
	}
}

void upd3(ll l, ll r, ll k, ll c) {
	for (ll e=E;e>=0;e--) {
		pdn3((l>>e)+(1<<(E-e)));
		pdn3((r>>e)+(1<<(E-e)));
	}
	aug3(l,r,k,c);
	for (ll e=0;e<=E;e++) {
		lft3((l>>e)+(1<<(E-e)));
		lft3((r>>e)+(1<<(E-e)));
	}
} 

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;
	}
	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});
			upd1(L,R,K);
			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({get1INF(A)-nq+B-1,A});
				//(get1(A)-nq)+(B-1)
			} else {
				qdpt.push_back({-1,-1});
			}
		}
	}
	ll gqi = 0; //global query index
	for (pii p0: qdpt) {
		ll a = p0.second; ll d = p0.first;
		if (d==-1) {
			ans[gqi]=0;
			gqi++;
			continue;
		}
		vqry[a].push_back({d,gqi});
		gqi++;
	}
	for (ll i=0;i<Nm;i++) {
		sort(vqry[i].begin(),vqry[i].end());
		for (ll t=(vqry[i].size()-1);t>=1;t--) {
			vqry[i][t].first-=vqry[i][t-1].first;
		}
		if (vqry[i].size()!=0) {
			st3[i+Nm]={vqry[i][0].first,i};
		} else {
			st3[i+Nm]={INF,INF};
		}
	}
	for (ll x=(Nm-1);x>=1;x--) {
		st3[x]=fz(st3[2*x],st3[2*x+1]);
	}
	for (auto A0: vupd) {
		if (A0[0]==1) {
			upd3(A0[1],A0[2],A0[4],A0[3]);
		}
	}
	for (ll x=0;x<gqi;x++) {
		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