제출 #555056

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
555056		kshitij_sodani	Fish 2 (JOI22_fish2)	C++14	8 / 100	4061 ms	30156 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 tree[4*100001][2];
void build(llo no,llo l,llo r){
	if(l==r){
		tree[no][0]=it[l]-pre[l];
		tree[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);
		tree[no][0]=max(tree[no*2+1][0],tree[no*2+2][0]);
		tree[no][1]=max(tree[no*2+1][1],tree[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 tree[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));
}
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;
/*	if(n<=500 and q<=500){
		while(q--){
			llo tt,l,r;
			cin>>tt>>l>>r;
			if(tt==1){
				l--;
				it[l]=r;
				
			}
			else{
				l--;
				r--;
				for(llo i=1;i<=n;i++){
					pre[i]=pre[i-1]+it[i-1];
				}
				if(l==r){
					cout<<1<<endl;
					continue;
				}
				if(it[l]>(pre[r+1]-pre[l+1])){
					cout<<1<<endl;
					continue;
				}
				if(it[r]>(pre[r]-pre[l])){
					cout<<1<<endl;
					continue;
				}
				set<llo> cur;
				for(llo ii=l;ii<=r;ii++){
					cur.insert(ii);
				}
				vector<llo> dd;
				for(llo j=l;j<=r;j++){
					for(llo k=j+2;k<=r;k++){
						if(pre[k]-pre[j+1]<it[j]){
							if(pre[k]-pre[j+1]<it[k]){
								//cout<<j<<":"<<k<<endl;
								auto jj=cur.lower_bound(j+1);
								while(jj!=cur.end()){
									if((*jj)<k){
										dd.pb((*jj));
										jj++;
									}
									else{
										break;
									}
								}
								for(auto jj:dd){
									cur.erase(jj);
								}
								dd.clear();
							}
						}
					}
				}
				for(llo j=l+1;j<=r;j++){
					if(it[j]>(pre[j]-pre[l])){
						cur.erase(l);
						break;
					}
				}
				for(llo j=r-1;j>=l;j--){
					if(it[j]>(pre[r+1]-pre[j+1])){
						cur.erase(r);
						break;
					}
				}
				cout<<cur.size()<<endl;

			}
		}
		return 0;
	}*/
	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==7){
			for(auto j:aa[i]){
				cout<<j<<",,";
			}
			cout<<endl;
		}*/
		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});
		}
	}		
	for(llo i=1;i<n;i++){
		if(pre[i]<it[i]){
			//ans--;
			break;
		}
	}

	for(llo i=n-2;i>=0;i--){
		if(it[i]>(pre[n]-pre[i+1])){
			//ans--;
			break;
		}
	}
	build(0,0,n-1);
	while(q--){
		llo tt,l,r;
		cin>>tt>>l>>r;
		if(tt==1){
			l--;
		}
		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=r;
			for(llo i=r-1;i>=l;i--){
				if(it[i]-(pre[r+1]-pre[i+1])>0){
					ind2=i;
				}
			}
			llo su=0;
			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;
		}
	}









	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