Submission #540513

#	Time	Username	Problem	Language	Result	Execution time	Memory
540513		alvingogo	Food Court (JOI21_foodcourt)	C++14	100 / 100	797 ms	92888 KiB

foodcourt

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define AquA cin.tie(0);ios_base::sync_with_stdio(0);
#define fs first
#define sc second
#define cd complex<double>
#define p_q priority_queue
#define int long long
using namespace std;
 
typedef pair<int,int> pii;
struct qu{
	int t;
	int l,r,c,k;
};
struct qu2{
	int t,p,k;
	int id;
};
bool cmp(qu2 a,qu2 b){
	if(a.p!=b.p){
		return a.p<b.p;
	}
	return a.t<b.t;
}
vector<qu> vq;
struct DS{
	struct no{
		vector<int> tag;
		int cnt=0;
	};
	vector<no> st;
	vector<int> kk;
	void init(int n){
		st.resize(4*n);
		kk.resize(n);
	}
	void upd(int v,int x){
		while(st[v].tag.size()){
			int y=st[v].tag.back();
			if(y<0 && x>0){
				break;
			}
			if(y>0 && x<0){
				st[v].cnt+=min(abs(y),abs(x));
				x+=y;
			}
			else{
				x+=y;
			}
			st[v].tag.pop_back();
		}
		if(x!=0){
			st[v].tag.push_back(x);
		}
	}
	void pudo(int v){
		st[2*v+1].cnt+=st[v].cnt;
		st[2*v+2].cnt+=st[v].cnt;
		for(auto y:st[v].tag){
			upd(2*v+1,y);
			upd(2*v+2,y);
		}
		st[v].cnt=0;
		st[v].tag.clear();
	}
	void update(int v,int L,int R,int l,int r,int k){
		if(l==L && r==R){
			upd(v,k);
			return;
		}
		pudo(v);
		int m=(L+R)/2;
		if(r<=m){
			update(2*v+1,L,m,l,r,k);
		}
		else if(l>m){
			update(2*v+2,m+1,R,l,r,k);
		}
		else{
			update(2*v+1,L,m,l,m,k);
			update(2*v+2,m+1,R,m+1,r,k);
		}
	}
	int query(int v,int L,int R,int pos){
		if(L==R){
			for(auto h:st[v].tag){
				if(h<0 && kk[L]>0){
					st[v].cnt+=min(abs(h),abs(kk[L]));
				}
				kk[L]+=h;
				kk[L]=max(kk[L],0ll);
			}
			st[v].tag.clear();
			return st[v].cnt;
		}
		pudo(v);
		int m=(L+R)/2;
		if(pos<=m){
			return query(2*v+1,L,m,pos);
		}
		else{
			return query(2*v+2,m+1,R,pos);
		}
	}
	void pre(int n){
		for(auto &h:vq){
			if(h.t==1){
				update(0,0,n-1,h.l,h.r,h.k);
			}
			else if(h.t==2){
				update(0,0,n-1,h.l,h.r,-h.k);
			}
			else{
				h.k+=query(0,0,n-1,h.l);
			}
		}
	}
};
struct Q13{
	vector<int> st;
	vector<qu2> g;
	void update(int v,int L,int R,int pos,int k){
		if(L==R){
			st[v]+=k;
			return;
		}
		int m=(L+R)/2;
		if(pos<=m){
			update(2*v+1,L,m,pos,k);
		}
		else{
			update(2*v+2,m+1,R,pos,k);
		}
		st[v]=st[2*v+1]+st[2*v+2];
	}
	int query(int v,int L,int R,int k){
		if(L==R){
			return L;
		}
		int m=(L+R)/2;
		if(st[2*v+1]>=k){
			return query(2*v+1,L,m,k);
		}
		else{
			return query(2*v+2,m+1,R,k-st[2*v+1]);
		}
	}
	void solve(int q){
		vector<int> ans(q,-1);
		vector<int> co(q,-1);
		st.resize(4*(q+1));
		for(int i=0;i<q;i++){
			if(vq[i].t==1){
				g.push_back({1,vq[i].l,vq[i].k,i});
				g.push_back({1,vq[i].r+1,-vq[i].k,i});
				co[i]=vq[i].c;
			}
			else if(vq[i].t==3){
				g.push_back({3,vq[i].l,vq[i].k,i});
			}
		}
		sort(g.begin(),g.end(),cmp);
		for(auto h:g){
			if(h.t==1){
				update(0,0,q,h.id,h.k);
			}
			else{
				int u=query(0,0,q,h.k);
				if(u>h.id){
					ans[h.id]=0;
				}
				else{
					ans[h.id]=co[u];
				}
			}
		}
		for(auto y:ans){
			if(y>=0){
				cout << y << "\n";
			}
		}
	}
};
signed main(){
	AquA;
	int n,m,q;
	cin >> n >> m >> q;
	vq.resize(q);
	for(int i=0;i<q;i++){
		cin >> vq[i].t;
		if(vq[i].t==1){
			cin >> vq[i].l >> vq[i].r >> vq[i].c >> vq[i].k;
			vq[i].l--;
			vq[i].r--;
		}
		else if(vq[i].t==2){
			cin >> vq[i].l >> vq[i].r >> vq[i].k;
			vq[i].l--;
			vq[i].r--;
		}
		else{
			cin >> vq[i].l >> vq[i].k;
			vq[i].l--;
		}
	}
	DS ds;
	ds.init(n);
	ds.pre(n);
	Q13 ss;
	ss.solve(q);
	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