Submission #1197031

#	Time	Username	Problem	Language	Result	Execution time	Memory
1197031		WH8	Food Court (JOI21_foodcourt)	C++20	13 / 100	583 ms	61332 KiB

foodcourt

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,m,q;

int fw[250005];
int timetosegind[250005];

struct query{
	int ind, posq, time,result;
	query(int _ind, int _posq, int _time, int _result=-2) 
		:ind(_ind), posq(_posq), time(_time), result(_result){}
	

};
	
struct seg{
	int l, r, time, comp, cont, posinsegs;
	seg(int _l,int _r, int _time, int _comp, int _cont)
		:l(_l), r(_r), time(_time), comp(_comp), cont(_cont){}
		
	//~ seg():l(-1), r(-1), time(-1), comp(-1),cont(-1),posinsegs(-1){}
};

void upd(int x,int v){
	if(x == 0)return;
	while(x <= q){
		fw[x]+=v;
		x+=(x&(-x));
	}
}
int qry(int x){
	int ret=0;
	while(x){
		ret+=fw[x];
		x-=(x&(-x));
	}
	return ret;
}

vector<query> qs; // ind, position, query index, queryt ime, result
vector<seg> segs; // l, r, company, contrib, companyindex, time;
vector<seg> segend; // l, r, company, contrib,companyindex, time;
vector<seg> segtime;
int N;
vector<int> v;

struct node{
    int S, E, M;
    int val;
    int mnval, secmn, nummin;
    int lazychmax, lazyadd;
    node *l, *r;
    node(int s, int e): S(s), E(e), M((s+e)/2), lazychmax(LLONG_MIN), lazyadd(0){
        if(s == e) {
            mnval = 0;
            nummin = 1;
            secmn = LLONG_MAX;
            return;
        }
        l = new node(S, M);
        r = new node(M+1, E);
        combine();
    }
    void prop(){
		if(lazyadd != 0){
			l->mnval+=lazyadd;
			if(l->secmn!=LLONG_MAX)l->secmn+=lazyadd;
			r->mnval+=lazyadd;
			if(r->secmn!=LLONG_MAX)r->secmn+=lazyadd;
			l->lazyadd+=lazyadd, r->lazyadd+=lazyadd;
			lazyadd=0;
		}
        if(lazychmax != LLONG_MIN){
            if(lazychmax > l->mnval) {
                l->mnval = lazychmax;
                l->lazychmax = max(l->lazychmax, lazychmax);
            }
            if(lazychmax > r->mnval) {
                r->mnval = lazychmax;
                r->lazychmax = max(r->lazychmax, lazychmax);
            }
            lazychmax = LLONG_MIN;
        }
    }
    void combine(){
        if(l->mnval < r->mnval) {
            mnval = l->mnval;
            nummin = l->nummin;
            secmn = min(l->secmn, r->mnval);
        }
        else if(l->mnval > r->mnval) {
            mnval = r->mnval;
            nummin = r->nummin;
            secmn = min(r->secmn, l->mnval);
        }
        else{
            mnval = l->mnval;
            nummin = l->nummin + r->nummin;
            secmn = min(l->secmn, r->secmn);
        }
    }
    void chmax(int x, int y, int k){
        if(x <= S && E <= y && secmn > k){
            if(mnval >= k) return;
            mnval = k;
            lazychmax = max(lazychmax, k);
            return;
        }
        prop();
        if(y <= M) l->chmax(x, y, k);
        else if(x > M) r->chmax(x, y, k);
        else{
            l->chmax(x, M, k);
            r->chmax(M+1, y, k);
        }
        combine();
    }
    void rangeadd(int x,int y,int k){
		if(x <= S && E <= y){
			lazyadd+=k;
			mnval+=k;
			if(secmn!=LLONG_MAX)secmn+=k;
			return;
		}
		prop();
		if(y <= M) l->rangeadd(x,y,k);
		else if(x > M)  r->rangeadd(x,y,k);
		else {
			l->rangeadd(x,M,k);
			r->rangeadd(M+1,y,k);
		}
		combine();
	}
    int qry(int x){
		if(S==E)return mnval;
		prop();
		if(x <= M) return l->qry(x);
		return r->qry(x);
	}
} *root;



signed main(){
	cin>>n>>m>>q;
	root=new node(1, n);
	for(int i=1;i<=q;i++){
		int t,a,b,l,r,c,k;cin>>t;
		if(t==1){
			cin>>l>>r>>c>>k;
			segs.push_back(seg(l,r,i,c,k));
			root->rangeadd(l,r,k);
		}
		else if(t==2){
			cin>>l>>r>>k;
			root->rangeadd(l, r, -k);
			root->chmax(l,r,0);
		}
		else{
			cin>>a>>b;
			int num=root->qry(a);
			//~ printf("\n %lld ppl at shop %lld \n",num,a);
			qs.push_back(query(a,num-b+1, i));
		}
	}
	sort(qs.begin(),qs.end(),[&](auto a,auto b){
		return a.ind<b.ind;
	});
	sort(segs.begin(),segs.end(),[&](auto a, auto b){
		return a.l<b.l;
	});
	for(int i=0;i<(int)segs.size();i++){
		segs[i].posinsegs=i;
	}
	for(auto it:segs)segend.push_back(it);
	sort(segend.begin(),segend.end(),[&](auto a, auto b){
		return a.r<b.r;
	});
	for(auto it:segs)segtime.push_back(it);
	sort(segtime.begin(),segtime.end(),[&](auto a, auto b){
		return a.time<b.time;
	});
	//~ for(auto it : qs){
		//~ cout<<it.ind<<" : " <<it.posq<<endl;
	//~ }
	//~ cout<<endl<<" segs : " << endl;
	//~ for(auto it : segs){
		//~ cout<<it.l<<" "<<it.r<<" "<<it.comp<<" "<<it.posinsegs<<endl;
	//~ }
	
	for(auto it : segs){
		timetosegind[it.time]=it.posinsegs;
	}
	
	int sptr=0, septr=0;
	for(auto & cq:qs){
		while(sptr < (int)segs.size() and segs[sptr].l <= cq.ind){
			upd(segs[sptr].time, segs[sptr].cont);
			sptr++;
		}
		while(septr<(int)segend.size() and segend[septr].r<cq.ind){
			upd(segend[septr].time, -segend[septr].cont);
			septr++;
		}

		//~ for(int i=0;i<=(int)segs.size();i++){
			//~ cout<<qry(i)<<" ";
		//~ }		
		
		//~ printf("query ind %lld, time %lld, posq %lld\n",cq.ind,cq.time,cq.posq);
		
		if(cq.posq<=0){
			cq.result=0;
			continue;
		}
		
		int hi,lo,m,ans;
		
		// determine from what max time such that between that time and cq.time, enuf occured 
		
		int os=qry(cq.time);
		//~ printf("os is %lld\n",os);
		hi=cq.time,lo=1, ans=0;
		while(hi>=lo){
			m=(hi+lo)/2;
			int res=os-qry(m-1);
			if(res>=cq.posq){
				ans=m;
				lo=m+1;
			}
			else{
				hi=m-1;
			}
		}
		
		//~ printf(" ans is %lld \n", ans);
		if(ans==0){
			cq.result=0;
			continue;
		}
		ans = timetosegind[ans];
		//~ printf("seg index is %lld\n",ans);
		cq.result=segs[ans].comp;
		
		//~ printf("res is %lld\n",cq.result);
	}	
	sort(qs.begin(),qs.end(), [&](auto a,auto b){
		return a.time<b.time;
	});
	for(auto it:qs){
		cout<<it.result<<"\n";
	}
		
}	

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