Submission #1020918

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020918		Unforgettablepl	Fish 2 (JOI22_fish2)	C++17	13 / 100	4081 ms	9792 KiB

fish2

// #pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define int long long

const int INF = 1e15;


int32_t main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin >> n;
	vector<int> arr(n+1);
	for(int i=1;i<=n;i++)cin>>arr[i];
	auto solve = [&](int l,int r){
		vector<int> left(n+1,l-1),right(n+1,r+1),pref(n+2);
		for(int i=l;i<=r;i++)pref[i]=pref[i-1]+arr[i];
		stack<pair<int,int>> s;
		s.emplace(INF,l-1);
		for(int i=l;i<=r;i++){
			while(s.top().first<=arr[i])s.pop();
			left[i]=s.top().second;
			s.emplace(arr[i],i);
		}
		while(!s.empty())s.pop();
		s.emplace(INF,r+1);
		for(int i=r;i>=l;i--){
			while(s.top().first<=arr[i])s.pop();
			right[i]=s.top().second;
			s.emplace(arr[i],i);
		}
		vector<vector<int>> adj(n+1);
		for(int i=l;i<=r;i++){
			if(left[i]==l-1 and right[i]==r+1)adj[left[i]].emplace_back(i);
			else if(left[i]==l-1)adj[right[i]].emplace_back(i);
			else if(right[i]==r+1)adj[left[i]].emplace_back(i);
			else if(arr[left[i]]<=arr[right[i]])adj[left[i]].emplace_back(i);
			else adj[right[i]].emplace_back(i);
		}
		int ans = 0;
		function<void(int,int)> dfs = [&](int x,int threshold){
			if(pref[right[x]-1]-pref[left[x]]<threshold)return;
			ans++;
			for(int&i:adj[x])dfs(i,arr[x]);
		};
		for(int&i:adj[l-1])dfs(i,0);
		return ans;
	};
	int q;
	cin >> q;
	for(int i=1;i<=q;i++){
		int type;cin>>type;
		if(type==1){
			int x,y;cin>>x>>y;
			arr[x]=y;
		} else {
			int l,r;cin>>l>>r;
			cout << solve(l,r) << '\n';
		}
	}
}

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