Submission #949910

#	Time	Username	Problem	Language	Result	Execution time	Memory
949910		amirhoseinfar1385	Food Court (JOI21_foodcourt)	C++17	0 / 100	16 ms	43612 KiB

foodcourt

#include<bits/stdc++.h>
using namespace std;
const int maxn=250000+10;
int n,m,q,res[maxn],kaf=(1<<19);
struct que{
	int l,r,t,k,c;
}allq[maxn];
struct node{
	long long summanf,begol,kamkon;
	node(){
		summanf=begol=kamkon=0;
	}
}fakenode;
struct segment{
	node seg[(1<<20)];
	node merge(node a,node b){
		node ret;
		ret.summanf=a.summanf+b.summanf;
		ret.begol=b.begol+max(0ll,a.begol-b.kamkon);
		ret.kamkon=a.kamkon+max(0ll,b.kamkon-a.begol);
		return ret;
	}
	void ins(int i){
		int fu=i;
		i+=kaf;
		if(allq[fu].t==1){
			seg[i].begol=allq[fu].k;
		}else{
			seg[i].summanf=seg[i].kamkon=allq[fu].k;
		}
		i>>=1;
		while(i>0){
			seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
			i>>=1;
		}
	}
	void reset(int i){
		int fu=i;
		i+=kaf;
		seg[i].summanf=seg[i].kamkon=seg[i].begol=0;
		i>>=1;
		while(i>0){
			seg[i]=merge(seg[(i<<1)],seg[(i<<1)^1]);
			i>>=1;
		}
	}
	node pors(int i,int l,int r,int tl,int tr){
		if(l>r||l>tr||r<tl||tl>tr){
			return fakenode;
		}
		if(l>=tl&&r<=tr){
			return seg[i];
		}
		int m=(l+r)>>1;
		return merge(pors((i<<1),l,m,tl,tr),pors((i<<1)^1,m+1,r,tl,tr));
	}
}seg;
vector<int>ins[maxn],del[maxn],por[maxn];

void vorod(){
	cin>>n>>m>>q;
	for(int i=1;i<=q;i++){
		cin>>allq[i].t;
		if(allq[i].t==1){
			cin>>allq[i].l>>allq[i].r>>allq[i].c>>allq[i].k;
		}else if(allq[i].t==2){
			cin>>allq[i].l>>allq[i].r>>allq[i].k;
		}else{
			cin>>allq[i].l>>allq[i].k;
		}
	}
}

void pre(){
	for(int i=1;i<=q;i++){
		if(allq[i].t==1){
			ins[allq[i].l].push_back(i);
			del[allq[i].r+1].push_back(i);
		}else if(allq[i].t==2){
			ins[allq[i].l].push_back(i);
			del[allq[i].r+1].push_back(i);
		}else{
			por[allq[i].l].push_back(i);
		}
	}
}

void pors(int ind){
	node unnow=seg.pors(1,0,kaf-1,0,ind);
	//cout<<"wtf: "<<ind<<" "<<unnow.begol<<" "<<unnow.kamkon<<endl;
	if(unnow.begol<allq[ind].k){
		res[ind]=0;
		return ;
	}
	int low=-1,high=ind,mid;
	while(high-low>1){
		mid=(high+low)>>1;
		unnow=seg.pors(1,0,kaf-1,0,mid);
		node bad=seg.pors(1,0,kaf-1,mid+1,ind);
		if(unnow.begol-bad.summanf>=allq[ind].k){
			high=mid;
		}else{
			low=mid;
		}
	}
	res[ind]=allq[high].c;
}

void solve(){
	for(int i=1;i<=n;i++){
		for(auto x:del[i]){
			seg.reset(x);
		}
		for(auto x:ins[i]){
			seg.ins(x);
		}
		for(auto x:por[i]){
			pors(x);
		}
	}	
}

void khor(){
	for(int i=1;i<=q;i++){
		if(allq[i].t==3){
			cout<<res[i]<<"\n";
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	freopen("inp.txt","r",stdin);
	vorod();
	pre();
	solve();
	khor();
}

Compilation message (stderr)

foodcourt.cpp: In member function 'void segment::reset(int)':
foodcourt.cpp:38:7: warning: unused variable 'fu' [-Wunused-variable]
   38 |   int fu=i;
      |       ^~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:135:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  135 |  freopen("inp.txt","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 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