Submission #386794

#	Time	Username	Problem	Language	Result	Execution time	Memory
386794		nathanlee726	Food Court (JOI21_foodcourt)	C++14	7 / 100	153 ms	146496 KiB

foodcourt

//#include<i_am_noob_orz>
#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
#define int ll
#define ull unsigned long long
#define pii pair<int,int>
#define X first
#define Y second
#define mod ((ll)1e9+7)
#define pb push_back
#define mp make_pair
#define abs(x) ((x)>0?(x):(-(x)))
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define memres(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
#define sz(a) ((int)a.size())
#define ceiling(a,b) (((a)+(b)-1)/(b))
#define endl '\n'
#define bit_count(x) __builtin_popcountll((x))
#define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define jimmy_is_kind false
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> rbtree;
 
//#define LOCAL
#ifdef LOCAL
#define bug(...) cerr<<"#"<<__LINE__<<' '<<#__VA_ARGS__<<"- ", _do(__VA_ARGS__)
template<typename T> void _do(T && x) {cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr<<x<<", "; _do(y...);}
#define IOS()
#else
#define IOS() ios_base::sync_with_stdio(0), cin.tie(0)
#define endl '\n'
#define bug(...)
#endif
 
int add(int a,int b){return(a+b>=mod?a+b-mod:a+b);}
int sub(int a,int b){return(a<b?a+mod-b:a-b);}
int po(int a,int b){
	if(b==0)return 1;
	if(b==1)return(a%mod);
	int tem=po(a,b/2);
	if(b&1)return(((tem*tem)%mod)*a)%mod;
	else return(tem*tem)%mod; 
}
int GCD(int a,int b){
	int x=0;
	int ra,rb;
	while(a&&b){
		if(((a&1)==0)&&((b&1)==0)){
			a>>=1,b>>=1,x++;
		}
		else if((a^b)&1){
			if(a&1)b>>=1;
			else a>>=1;
		}
		else{
			ra=abs(a-b),rb=min(a,b);
			a=ra,b=rb;
		}
	}
	return max(a,b)<<x;
}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int n,m,q;
struct segment_tree{
	struct NODE{
		vector<pii> ve;
		queue<pii> tg;
		int mi,v,tt;
		NODE():mi(0),v(0),tt(0){}
		int bs(int l,int r,int vl){
			if(l==r){
				return ve[l].Y;
			}
			int mi=(l+r)/2;
			bug(mi,ve[mi].X,vl);
			if(ve[mi].X>=vl)return bs(l,mi,vl);
			else return bs(mi+1,r,vl);
		}
	}seg[100010];
	void push(int p){
		while(!seg[p].tg.empty()){
			if(seg[p].tg.front().Y==-1){
				seg[p*2].mi=min(seg[p*2].v,seg[p*2].mi+seg[p].tg.front().X);
				seg[p*2+1].mi=min(seg[p*2+1].v,seg[p*2+1].mi+seg[p].tg.front().X);
				bug(p*2+1,seg[p*2+1].mi,seg[p].tg.front().X);
			}
			else{
				seg[p*2].v+=seg[p].tg.front().X;
				seg[p*2].ve.pb({seg[p*2].v,seg[p].tg.front().Y});
				seg[p*2+1].v+=seg[p].tg.front().X;
				seg[p*2+1].ve.pb({seg[p*2+1].v,seg[p].tg.front().Y});
			}
			seg[p*2].tg.push(seg[p].tg.front());
			seg[p*2+1].tg.push(seg[p].tg.front());
			seg[p].tg.pop();
		}
	}
	void insert(int p,int l,int r,int ql,int qr,pii vl){
		if(l>qr||r<ql)return;
		if(l>=ql&&r<=qr){
			seg[p].v+=vl.X;
			seg[p].ve.pb({seg[p].v,vl.Y});
			seg[p].tg.push(vl);
			return;
		}
		int mi=(l+r)/2;
		push(p);
		insert(p*2,l,mi,ql,qr,vl);
		insert(p*2+1,mi+1,r,ql,qr,vl);
		return;
	}
	void erase(int p,int l,int r,int ql,int qr,int vl){
		if(l>qr||r<ql)return;
		if(l>=ql&&r<=qr){
			seg[p].mi=min(seg[p].v,seg[p].mi+vl);
			bug(seg[p].mi,seg[p].v);
			seg[p].tg.push({vl,-1});
			return;
		}
		int mi=(l+r)/2;
		push(p);
		erase(p*2,l,mi,ql,qr,vl);
		erase(p*2+1,mi+1,r,ql,qr,vl);
		return;
	}
	int qry(int p,int l,int r,int x,int vl){
		if(l==r){
			bug(p,seg[p].mi,vl,seg[p].v,sz(seg[p].ve)-1);
			if(seg[p].mi+vl>seg[p].v)return 0;
			else return seg[p].bs(0,sz(seg[p].ve)-1,seg[p].mi+vl);
		}
		int mi=(l+r)/2;
		push(p);
		if(mi>=x)return qry(p*2,l,mi,x,vl);
		else return qry(p*2+1,mi+1,r,x,vl);
	}
}sgt;
signed main(){
	IOS();
	cin>>n>>m>>q;
	while(q--){
		int ty;
		cin>>ty;
		if(ty==1){
			int l,r,c,k;
			cin>>l>>r>>c>>k;
			--l,--r;
			sgt.insert(1,0,n-1,l,r,{k,c});
		}
		else if(ty==2){
			int l,r,k;
			cin>>l>>r>>k;
			--l,--r;
			sgt.erase(1,0,n-1,l,r,k);
		} 
		else{
			int x,y;
			cin>>x>>y;
			--x;
			cout<<sgt.qry(1,0,n-1,x,y)<<endl;
		}
	}
	return 0;
}

• Subtask 1: 2 / 2
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11