Submission #955348

#	Time	Username	Problem	Language	Result	Execution time	Memory
955348		LCJLY	Food Court (JOI21_foodcourt)	C++14	100 / 100	697 ms	104092 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,pii>pi2;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int n,m,q;

inline int combine(int a, int b){
	return min(a,b);
}

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	int lazyUpd;

	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),lazyUpd(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void self_add(int x){
		v+=x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyUpd){
			l->self_add(lazyUpd),r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m) return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
	
	int walk(int need){
		if(s==e){
			if(v<=need) return -1;
			return s;
		}
		forceProp();
		if(r->v<=need) return r->walk(need);
		else{
			int hold=l->walk(need);
			if(hold==-1){
				return r->walk(need);
			}
			return hold;
		}
	}
};

void solve(){
	cin >> n >> m >> q;
	
	vector<pii>add[n+5]; //time val
	vector<pii>minus[n+5]; 
	vector<pii>que[n+5];
	int index[q+5];
	
	int temp,temp2,temp3,temp4,temp5;
	for(int x=1;x<=q;x++){
		cin >> temp;
		if(temp==1){
			cin >> temp2 >> temp3 >> temp4 >> temp5;
			index[x]=temp4;
			add[temp2].push_back({x,temp5});
			minus[temp3+1].push_back({x,-temp5});
		}
		else if(temp==2){
			cin >> temp2 >> temp3 >> temp4;
			add[temp2].push_back({x,-temp4});
			minus[temp3+1].push_back({x,temp4});
		}
		else{
			cin >> temp2 >> temp3;
			que[temp2].push_back({x,temp3});
			//show3(temp2,temp2,x,x,temp3,temp3);
		}
	}
	
	node st(0,q);
	node st2(0,q);
	
	int ans[q+5];
	memset(ans,-1,sizeof(ans));
	
	for(int x=1;x<=n;x++){
		//show(pos,x);
		for(auto it:add[x]){
			st.rangeUpd(it.first,q,it.second);
			//show2(it.first,it.first,it.second,it.second);
			if(it.second>0){
				st2.rangeUpd(it.first,q,it.second);
			}
		}
		for(auto it:minus[x]){
			st.rangeUpd(it.first,q,it.second);
			//show2(it2.first,it.first,it2.second,it.second);
			if(it.second<0){
				st2.rangeUpd(it.first,q,it.second);
			}	
		}
		
		for(auto it:que[x]){
			int need=it.second;
			int hold=st.query(0,it.first);
			int hold2=st.query(it.first,it.first);
			//show3(need,need,hold,hold,hold2,hold2);
			if(hold2-hold<need){
				ans[it.first]=0;
			}
			else{
				int hold3=st2.query(it.first,it.first);
				int diff=hold2-hold-need;
				int take=hold3-diff-1;
				//show3(hold3,hold3,diff,diff,take,take);
				
				int take2=st2.walk(take);
				//show(walk,take2);
				//show(index[take2],index[take2]);
				ans[it.first]=index[st2.walk(take)];
			}
		}
	}
	
	//show4(ans,ans);
	
	for(int x=1;x<=q;x++){
		if(ans[x]==-1) continue;
		cout << ans[x] << "\n";
	}
	
}	
 
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int t=1;
	//cin >> t;
	while(t--){
		solve();
	}
}

Compilation message (stderr)

foodcourt.cpp: In function 'void solve()':
foodcourt.cpp:150:9: warning: unused variable 'take2' [-Wunused-variable]
  150 |     int take2=st2.walk(take);
      |         ^~~~~

• 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