Submission #1093902

#	Time	Username	Problem	Language	Result	Execution time	Memory
1093902		emptypringlescan	Food Court (JOI21_foodcourt)	C++17	100 / 100	538 ms	91736 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
struct node{
	int s,e,m;
	long long sumneg,val,ppl,lazy;
	int col;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		sumneg=val=ppl=lazy=0;
		col=-1;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	void prop(){
		if(s==e) return;
		if(lazy){
			l->val+=lazy;
			l->lazy+=lazy;
			r->val+=lazy;
			r->lazy+=lazy;
			lazy=0;
		}
	}
	void radd(int S, int E, long long V){
		if(S<=s&&e<=E){
			val+=V;
			lazy+=V;
			return;
		}
		prop();
		if(E<=m) l->radd(S,E,V);
		else if(S>m) r->radd(S,E,V);
		else l->radd(S,m,V),r->radd(m+1,E,V);
		val=min(l->val,r->val);
	}
	void sneg(int S, long long V){
		if(s==e){
			sumneg=V;
			return;
		}
		prop();
		if(S<=m) l->sneg(S,V);
		else r->sneg(S,V);
		sumneg=l->sumneg+r->sumneg;
	}
	void sppl(int S, long long V, int C){
		if(s==e){
			ppl=V;
			col=C;
			return;
		}
		prop();
		if(S<=m) l->sppl(S,V,C);
		else r->sppl(S,V,C);
		ppl=l->ppl+r->ppl;
	}
	long long qval(int S, int E){
		if(S<=s&&e<=E) return val;
		prop();
		if(E<=m) return l->qval(S,E);
		else if(S>m) return r->qval(S,E);
		else return min(l->qval(S,m),r->qval(m+1,E));
	}
	long long qsum(int S, int E){
		if(S<=s&&e<=E) return sumneg;
		prop();
		if(E<=m) return l->qsum(S,E);
		else if(S>m) return r->qsum(S,E);
		else return l->qsum(S,m)+r->qsum(m+1,E);
	}
	pair<int,int> bsta(long long V){
		if(s==e){
			//assert(V<=ppl||ppl==0);
			return {s,col};
		}
		prop();
		if(l->ppl>=V) return l->bsta(V);
		else return r->bsta(V-l->ppl);
	}
} *root;
int32_t main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,q;
    cin >> n >> m >> q;
    long long ans[q];
    memset(ans,-1,sizeof(ans));
    vector<pair<int,pair<long long,int> > > st[n+5],en[n+5];
    vector<pair<int,long long> > st2[n+5],en2[n+5];
    vector<pair<int,long long> > qu[n+5];
    root=new node(0,q);
    for(int i=0; i<q; i++){
		int cmd;
		cin >> cmd;
		if(cmd==1){
			int l,r,c;
			long long k;
			cin >> l >> r >> c >> k;
			st[l].push_back({i,{k,c}});
			en[r].push_back({i,{k,c}});
		}
		else if(cmd==2){
			int l,r;
			long long k;
			cin >> l >> r >> k;
			st2[l].push_back({i,k});
			en2[r].push_back({i,k});
		}
		else{
			int a;
			long long b;
			cin >> a >> b;
			qu[a].push_back({i,b});
		}
	}
	for(int i=1; i<=n; i++){
		for(auto [x,y]:st[i]){
			root->sppl(x,y.first,y.second);
			root->radd(x,q,y.first);
		}
		for(auto [x,y]:st2[i]){
			root->sneg(x,y);
			root->radd(x,q,-y);
		}
		for(auto [x,y]:qu[i]){
			//cout << "hi";
			long long smol=root->qval(0,x);
			//cout << smol << ' ';
			long long off=root->qsum(0,x)+y;
			//cout << off << ' ';
			if(smol<0) off+=smol;
			pair<int,int> yey=root->bsta(off);
			//cout << yey.first << ',' << yey.second << ' ';
			if(yey.first>x) ans[x]=0;
			else ans[x]=yey.second;
			//cout << ans[x] << '\n';
		}
		for(auto [x,y]:en[i]){
			root->sppl(x,0,-1);
			root->radd(x,q,-y.first);
		}
		for(auto [x,y]:en2[i]){
			root->sneg(x,0);
			root->radd(x,q,y);
		}
	}
	for(int i=0; i<q; i++) if(ans[i]!=-1) cout << ans[i] << '\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