Submission #555073

#	Time	Username	Problem	Language	Result	Execution time	Memory
555073		kshitij_sodani	Fish 2 (JOI22_fish2)	C++14	8 / 100	1670 ms	186020 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define a first
#define b second
#define pb push_back
#define endl '\n'

llo it[100001];
vector<llo> aa[100001];
llo pre[100001];
vector<pair<llo,llo>> bb[100001];
vector<pair<llo,llo>> cc[100001];
pair<llo,llo> ne[100001];
llo fin[100001];
llo tree2[4*100001][2];
vector<pair<pair<llo,llo>,pair<llo,llo>>> ee[100001];
vector<pair<llo,llo>> ff[100001];
void build(llo no,llo l,llo r){
	if(l==r){
		tree2[no][0]=it[l]-pre[l];
		tree2[no][1]=it[l]+pre[l+1];
	}
	else{
		llo mid=(l+r)/2;
		build(no*2+1,l,mid);
		build(no*2+2,mid+1,r);
		tree2[no][0]=max(tree2[no*2+1][0],tree2[no*2+2][0]);
		tree2[no][1]=max(tree2[no*2+1][1],tree2[no*2+2][1]);
	}
}
llo query(llo no,llo l,llo r,llo aa,llo bb,llo ind){
	if(r<aa or l>bb or aa>bb){
		return -(llo)1e18;
	}
	if(aa<=l and r<=bb){
		return tree2[no][ind];
	}
	llo mid=(l+r)/2;
	return max(query(no*2+1,l,mid,aa,bb,ind),query(no*2+2,mid+1,r,aa,bb,ind));
}

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ord tree<pair<llo,llo>,null_type,less<pair<llo,llo>>,rb_tree_tag,tree_order_statistics_node_update>
ord tree3[4*100001];
void update2(llo no,llo l,llo r,llo i,llo j){
	tree3[no].insert({j,i});
	if(l<r){
		llo mid=(l+r)/2;
		if(i<=mid){
			update2(no*2+1,l,mid,i,j);
		}
		else{
			update2(no*2+2,mid+1,r,i,j);
		}
	}
}
llo query2(llo no,llo l,llo r,llo aa,llo bb,llo i){
	if(r<aa or l>bb or aa>bb){
		return 0;
	}
	if(aa<=l and r<=bb){
		if(tree3[no].size()==0){
			return 0;
		}

		//for(auto j:tree3[no]){
		//	cout<<j.a<<","<<j.b<<endl;
		//}
		return tree3[no].order_of_key({i,-1});
	}
	llo mid=(l+r)/2;
	return query2(no*2+1,l,mid,aa,bb,i)+query2(no*2+2,mid+1,r,aa,bb,i);
}
llo cot[100001];
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,q;
	cin>>n;
	for(llo i=0;i<n;i++){
		cin>>it[i];
		pre[i+1]=pre[i]+it[i];
	}
	cin>>q;

	for(llo i=0;i<n;i++){
		ne[i]={-1,-1};
	}
	for(llo i=1;i<n;i++){
		if(it[i]<it[i-1]){
			aa[i].pb(i);
		}
		for(auto j:aa[i-1]){
			if(pre[i+1]-pre[j]<it[j-1]){
				aa[i].pb(j);
			}
		}

		if(i<n-1){
			for(auto j:aa[i]){
				if(pre[i+1]-pre[j]<it[i+1]){
					bb[j-1].pb({i,j});
					cc[i+1].pb({i,j});
					//cout<<i<<":"<<j<<endl;

				}
			}
		}
	}
	multiset<pair<llo,llo>> cur;
	llo ans=n;
	for(llo i=0;i<n;i++){
		for(auto j:cc[i]){
			auto jj=cur.find({j.a,-j.b});
			cur.erase(jj);
		}
		if(cur.size()){
			pair<llo,llo> no=*(cur.begin());
			no.b=-no.b;
			ans--;
			ne[i]={no.b,no.a};
		}
		else{
		}
		for(auto j:bb[i]){
			cur.insert({j.a,-j.b});
		}
	}		
	build(0,0,n-1);
	llo zz=0;
	while(q--){
		llo tt,l,r;
		cin>>tt>>l>>r;
		if(tt==1){
			l--;
			it[l]=r;

			for(llo i=0;i<n;i++){
				ne[i]={-1,-1};
				aa[i].clear();
				bb[i].clear();
				cc[i].clear();
			}
			for(int i=0;i<n;i++){
				pre[i+1]=pre[i]+it[i];
			}
			for(llo i=1;i<n;i++){
				if(it[i]<it[i-1]){
					aa[i].pb(i);
				}
				for(auto j:aa[i-1]){
					if(pre[i+1]-pre[j]<it[j-1]){
						aa[i].pb(j);
					}
				}

				if(i<n-1){
					for(auto j:aa[i]){
						if(pre[i+1]-pre[j]<it[i+1]){
							bb[j-1].pb({i,j});
							cc[i+1].pb({i,j});
							//cout<<i<<":"<<j<<endl;

						}
					}
				}
			}
			multiset<pair<llo,llo>> cur;
			llo ans=n;
			for(llo i=0;i<n;i++){
				for(auto j:cc[i]){
					auto jj=cur.find({j.a,-j.b});
					cur.erase(jj);
				}
				if(cur.size()){
					pair<llo,llo> no=*(cur.begin());
					no.b=-no.b;
					ans--;
					ne[i]={no.b,no.a};
				}
				else{
				}
				for(auto j:bb[i]){
					cur.insert({j.a,-j.b});
				}
			}		
			build(0,0,n-1);
		}
		else{
			l--;
			r--;
			if(l==r){
				cout<<1<<endl;
				continue;
			}
			llo ind=r+1;
			for(llo j=19;j>=0;j--){
				if(ind-(1<<j)>l){
					if(query(0,0,n-1,ind-(1<<j),r,0)+pre[l]<=0){
						//cout<<query(0,0,n-1,ind-(1<<j),r,0)+pre[l]<<","<<ind-(1<<j)<<","<<r<<endl;
						ind-=(1<<j);
					}
				}
			}
			ind--;
			//cout<<ind<<":"<<endl;
		/*	llo ind=low-1;
			for(llo i=l+1;i<=r;i++){
				if(it[i]-(pre[i]-pre[l])>0){
					ind=i;
				}
			}*/
			llo ind2=l-1;
			for(llo j=19;j>=0;j--){
				if(ind2+(1<<j)<r){
					if(query(0,0,n-1,l,ind2+(1<<j),1)-pre[r+1]<=0){
						ind2+=(1<<j);
					}
				}
			}
			ind2++;
			/*for(llo i=r-1;i>=l;i--){
				if(it[i]-(pre[r+1]-pre[i+1])>0){
					ind2=i;
				}
			}
			ind2++;*/

			llo su=0;
			if(ind>ind2){
				fin[zz]=0;
			}
			else{
				ee[l].pb({{ind,ind2},{r,zz}});
			}
			for(llo j=ind;j<=ind2;j++){
				if(ne[j].a>=0){
					if(ne[j].a>l and ne[j].b<r){
						continue;
					}
				}
				su++;
			}
			//cout<<su<<endl;
			zz++;
		}
	}

	for(llo i=0;i<n;i++){
		if(ne[i].a>=0){
			//cout<<i<<":"<<ne[i].a<<":"<<ne[i].b<<endl;
			ff[ne[i].a].pb({i,ne[i].b});
		}

	}
	for(int i=0;i<n;i++){
		cot[i]=n;
	}
	for(llo i=n-1;i>=0;i--){
		for(auto j:ee[i]){
			llo xx=(j.a.b-j.a.a+1)-query2(0,0,n-1,j.a.a,j.a.b,j.b.a);
			/*for(int ii=j.a.a;ii<=j.a.b;ii++){
				if(cot[ii]<j.b.a){

				}
				else{
					xx++;
				}
			}*/
		//	cout<<i<<","<<j.a.a<<","<<j.a.b<<","<<j.b.a<<","<<j.b.b<<endl;
			//cout<<xx<<endl;
			//xx=(j.a.b-j.a.a+1)-xx;
			fin[j.b.b]=xx;
		}
		for(auto j:ff[i]){
			//cout<<j.a<<"::"<<j.b<<endl;
			cot[j.a]=j.b;
			update2(0,0,n-1,j.a,j.b);
		}
	}


	for(llo i=0;i<zz;i++){
		cout<<fin[i]<<endl;
	}








	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17