Submission #1026314

#	Time	Username	Problem	Language	Result	Execution time	Memory
1026314		Unforgettablepl	Fish 2 (JOI22_fish2)	C++17	31 / 100	337 ms	25436 KiB

fish2

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;

struct node{
	int ele,cnt;
	node(int x=INT64_MIN):ele(x),cnt(1){}
	node(const node &a,const node &b):ele(max(a.ele,b.ele)),cnt(0){
		if(a.ele==ele)cnt+=a.cnt;
		if(b.ele==ele)cnt+=b.cnt;
	}
};

struct segtree{
	vector<node> tree;
	segtree():tree(262144){}
	void update(int k,int x){
		k+=131072;
		tree[k]=x;
		while(k/=2){
			tree[k]={tree[2*k],tree[2*k+1]};
		}
	}
	pair<int,int> get(int l,int r){
		node ans;l+=131072;r+=131072;
		while(l<=r){
			if(l&1)ans={ans,tree[l++]};
			if(r%2 == 0)ans={ans,tree[r--]};
			l/=2;r/=2;
		}
		return {ans.ele,ans.cnt};
	}
};

int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<long long> arr(n+2);
	for(int i=1;i<=n;i++)cin>>arr[i];
	arr[0]=arr[n+1]=INF;
	segtree cntranges;
	segtree sumtree;
	segtree sumtree2;
	vector<int> sums(n+2);
	vector<int> ranges(n+2);
	sums[0]=arr[0];
	for(int i=1;i<=n+1;i++)sums[i]=sums[i-1]+arr[i];
	{
		stack<pair<int,int>> s;
		s.emplace(arr[0],0);
		for(int i=1;i<=n;i++){
			while(s.top().first<arr[i])s.pop();
			if(sums[i-1]-sums[s.top().second] < arr[i]){
				ranges[s.top().second+1]++;
				ranges[i]--;
			}
			s.emplace(arr[i],i);
		}
	}
	{
		stack<pair<int,int>> s;
		s.emplace(arr[n+1],n+1);
		for(int i=n;i;i--){
			while(s.top().first<=arr[i])s.pop();
			if(sums[s.top().second-1]-sums[i] < arr[i]){
				ranges[i+1]++;
				ranges[s.top().second]--;
			}
			s.emplace(arr[i],i);
		}
	}
	for(int i=1;i<=n+1;i++)ranges[i]+=ranges[i-1];
	for(int i=1;i<=n;i++){
		cntranges.update(i,-ranges[i]);
		sumtree.update(i,arr[i]-sums[i-1]);
		sumtree2.update(i,arr[i]+sums[i]);
	}
	int q;
	cin >> q;
	for(int i=1;i<=q;i++){
		int type;cin>>type;
		int l,r;cin>>l>>r;
		int ld = r;
		int rd = l;
		{
			// transform query
			for(int jump=65536;jump;jump/=2){
				if(ld-jump<l)continue;
				if(sumtree.get(ld-jump+1,r).first<=-sums[l-1])ld-=jump;
			}
			for(int jump=65536;jump;jump/=2){
				if(rd+jump>r)continue;
				if(sumtree2.get(l,rd+jump-1).first<=sums[r])rd+=jump;
			}
		}
		assert(ld<=rd);
		cout << cntranges.get(ld,rd).second << '\n';
	}
}

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