Submission #1215501

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215501		emptypringlescan	Fish 2 (JOI22_fish2)	C++17	25 / 100	1801 ms	63932 KiB

fish2

#include <bits/stdc++.h>
using namespace std;
bool st3;
int n,q;
long long arr[100005];
struct node{
	int s,e,m;
	pair<long long,int> val;
	node *l,*r;
	node(int S, int E){
		s=S; e=E; m=(s+e)/2;
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
			val=max(l->val,r->val);
		}
		else val={arr[s],s};
	}
	pair<long long,int> query(int S, int E){
		if(S<=s&&e<=E) return val;
		if(E<=m) return l->query(S,E);
		else if(S>m) return r->query(S,E);
		else return max(l->query(S,m),r->query(m+1,E));
	}
} *root;
vector<pair<int,int> > bad;
pair<int,int> nxt[2][100005];
pair<pair<int,int>,int> twok[2][20][100005];
long long pref[100005];
void recons(){
	pref[0]=0;
	for(int i=1; i<=n; i++) pref[i]=pref[i-1]+arr[i];
	bad.clear();
	vector<pair<long long,int> > mono={{1e9,0}};
	for(int i=1; i<=n; i++){
		while(!mono.empty()&&mono.back().first<arr[i]){
			if(mono.back().second<i-1&&pref[i-1]-pref[mono.back().second]<min(arr[i],mono.back().first)){
				bad.push_back({mono.back().second+1,i-1});
			}
			mono.pop_back();
		}
		if(mono.back().second<i-1&&pref[i-1]-pref[mono.back().second]<min(arr[i],mono.back().first)){
			bad.push_back({mono.back().second+1,i-1});
		}
		mono.push_back({arr[i],i});
	}
	while(!mono.empty()){
		if(mono.back().second<n&&pref[n]-pref[mono.back().second]<mono.back().first){
			bad.push_back({mono.back().second+1,n});
		}
		mono.pop_back();
	}
	//for(auto i:bad) cout << i.first << ' ' << i.second << '\n';
	for(int i=0; i<=n; i++) nxt[0][i]=nxt[1][i]={-1,-1};
	for(auto i:bad){
		if(i.first>1){
			if(nxt[0][i.first-1].first==-1||nxt[0][i.first-1].second<i.second) nxt[0][i.first-1]=i;
		}
		if(i.second<n){
			if(nxt[1][i.second+1].first==-1||nxt[1][i.second+1].first>i.first) nxt[1][i.second+1]=i;
		}
	}
	pair<int,int> cur={-1,-1};
	for(int i=1; i<=n; i++){
		if(nxt[1][i].first==-1) nxt[1][i]=cur;
		else cur=nxt[1][i];
	}
	cur={-1,-1};
	for(int i=n; i>0; i--){
		if(nxt[0][i].first==-1) nxt[0][i]=cur;
		else cur=nxt[0][i];
	}
	if(!st3){
		for(int i=0; i<2; i++) for(int j=0; j<20; j++) for(int k=0; k<=n; k++) twok[i][j][k]={{-1,-1},-1};
		for(int i=1; i<=n; i++){
			twok[0][0][i]={nxt[0][i],nxt[0][i].second-nxt[0][i].first+1};
			twok[1][0][i]={nxt[1][i],nxt[1][i].second-nxt[1][i].first+1};
		}
		for(int i=0; i<19; i++){
			for(int j=1; j<=n; j++){
				if(twok[0][i][j].first.first!=-1){
					twok[0][i+1][j].first=twok[0][i][twok[0][i][j].first.second+1].first;
					twok[0][i+1][j].second=twok[0][i][j].second+twok[0][i][twok[0][i][j].first.second+1].second;
				}
				if(twok[1][i][j].first.first!=-1){
					twok[1][i+1][j].first=twok[1][i][twok[1][i][j].first.first-1].first;
					twok[1][i+1][j].second=twok[1][i][j].second+twok[1][i][twok[1][i][j].first.first-1].second;
				}
			}
		}
	}
}
int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++) cin >> arr[i];
	cin >> q;
	if(q<=1000) st3=true;
	else{
		st3=false;
		root=new node(1,n);
	}
	recons();
	while(q--){
		int cmd;
		cin >> cmd;
		if(cmd==1){
			int x;
			long long y;
			cin >> x >> y;
			arr[x]=y;
			recons();
		}
		else{
			int a,b;
			cin >> a >> b;
			if(!st3){
				int big=root->query(a,b).second;
				int tbad=0;
				int cur=big;
				for(int i=19; i>=0; i--){
					if(twok[0][i][cur].first.first!=-1&&twok[0][i][cur].first.second<=b){
						tbad+=twok[0][i][cur].second;
						cur=twok[0][i][cur].first.second+1;
					}
				}
				if(twok[0][0][cur].first.first!=-1&&twok[0][0][cur].first.first<=b){
					assert(twok[0][0][cur].first.second>b);
					tbad+=b-twok[0][0][cur].first.first+1;
				}
				cur=big;
				for(int i=19; i>=0; i--){
					if(twok[1][i][cur].first.first!=-1&&twok[1][i][cur].first.first>=a){
						tbad+=twok[1][i][cur].second;
						cur=twok[1][i][cur].first.first-1;
					}
				}
				if(twok[1][0][cur].first.first!=-1&&twok[1][0][cur].first.second>=a){
					assert(twok[0][0][cur].first.first<a);
					tbad+=twok[1][0][cur].first.second-a+1;
				}
				cout << b-a+1-tbad << '\n';
			}
			else{
				int wall=a;
				for(int i=a; i<=b; i++){
					if(arr[i]-pref[i-1]+pref[a-1]>0) wall=i;
				}
				a=wall;
				wall=b;
				for(int i=b; i>=a; i--){
					if(arr[i]-pref[b]+pref[i]>0) wall=i;
				}
				b=wall;
				pair<long long,int> big={-1,-1};
				for(int i=a; i<=b; i++) big=max(big,make_pair(arr[i],i));
				int tbad=0;
				int cur=big.second;
				while(cur<=b){
					if(nxt[0][cur].first==-1) break;
					if(nxt[0][cur].second<=b){
						tbad+=nxt[0][cur].second-nxt[0][cur].first+1;
						cur=nxt[0][cur].second+1;
					}
					else if(nxt[0][cur].first<=b){
						tbad+=b-nxt[0][cur].first+1;
						break;
					}
					else break;
				}
				cur=big.second;
				while(cur>=a){
					if(nxt[1][cur].first==-1) break;
					if(nxt[1][cur].first>=a){
						tbad+=nxt[1][cur].second-nxt[1][cur].first+1;
						cur=nxt[1][cur].first-1;
					}
					else if(nxt[1][cur].second>=a){
						tbad+=nxt[1][cur].second-a+1;
						break;
					}
					else break;
				}
				cout << b-a+1-tbad << '\n';
			}
		}
	}
}

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