oj.uz

Submission #1020920

# Submission time Handle Problem Language Result Execution time Memory
1020920 2024-07-12T11:27:30 Z Unforgettablepl Fish 2 (JOI22_fish2) C++17
0 / 100
 12 ms 7740 KB 
#pragma GCC optimize("Ofast","unroll-loops")
#include <bits/stdc++.h>
using namespace std;

// #define int long long

const int INF = INT32_MAX;


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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 12 ms 7740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 12 ms 7740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 12 ms 7740 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Incorrect 1 ms 348 KB Output isn't correct
6 Halted 0 ms 0 KB -