oj.uz

Submission #1020922

# Submission time Handle Problem Language Result Execution time Memory
1020922 2024-07-12T11:28:48 Z Unforgettablepl Fish 2 (JOI22_fish2) C++17
13 / 100
 4000 ms 9984 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<long long> 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);
		vector<long long> 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 2 ms 496 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Correct 5 ms 344 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 10 ms 504 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 13 ms 8532 KB Output is correct
3 Correct 11 ms 7516 KB Output is correct
4 Correct 12 ms 8540 KB Output is correct
5 Correct 11 ms 7768 KB Output is correct
6 Correct 16 ms 8028 KB Output is correct
7 Correct 11 ms 6748 KB Output is correct
8 Correct 17 ms 7984 KB Output is correct
9 Correct 12 ms 7000 KB Output is correct
10 Correct 12 ms 7516 KB Output is correct
11 Correct 11 ms 6492 KB Output is correct
12 Correct 12 ms 7256 KB Output is correct
13 Correct 12 ms 7260 KB Output is correct
14 Correct 13 ms 7260 KB Output is correct
15 Correct 14 ms 7736 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 2 ms 496 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Correct 5 ms 344 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 10 ms 504 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 13 ms 8532 KB Output is correct
23 Correct 11 ms 7516 KB Output is correct
24 Correct 12 ms 8540 KB Output is correct
25 Correct 11 ms 7768 KB Output is correct
26 Correct 16 ms 8028 KB Output is correct
27 Correct 11 ms 6748 KB Output is correct
28 Correct 17 ms 7984 KB Output is correct
29 Correct 12 ms 7000 KB Output is correct
30 Correct 12 ms 7516 KB Output is correct
31 Correct 11 ms 6492 KB Output is correct
32 Correct 12 ms 7256 KB Output is correct
33 Correct 12 ms 7260 KB Output is correct
34 Correct 13 ms 7260 KB Output is correct
35 Correct 14 ms 7736 KB Output is correct
36 Correct 887 ms 8448 KB Output is correct
37 Correct 1295 ms 7420 KB Output is correct
38 Correct 1516 ms 8964 KB Output is correct
39 Correct 365 ms 9576 KB Output is correct
40 Correct 1636 ms 9124 KB Output is correct
41 Correct 1923 ms 9984 KB Output is correct
42 Correct 2509 ms 9444 KB Output is correct
43 Correct 1514 ms 8312 KB Output is correct
44 Correct 1836 ms 8428 KB Output is correct
45 Correct 782 ms 7252 KB Output is correct
46 Correct 1129 ms 7348 KB Output is correct
47 Correct 1488 ms 8328 KB Output is correct
48 Correct 614 ms 7168 KB Output is correct
49 Correct 2064 ms 7428 KB Output is correct
50 Correct 1079 ms 8960 KB Output is correct
51 Execution timed out 4075 ms 7760 KB Time limit exceeded
52 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 13 ms 8532 KB Output is correct
3 Correct 11 ms 7516 KB Output is correct
4 Correct 12 ms 8540 KB Output is correct
5 Correct 11 ms 7768 KB Output is correct
6 Correct 16 ms 8028 KB Output is correct
7 Correct 11 ms 6748 KB Output is correct
8 Correct 17 ms 7984 KB Output is correct
9 Correct 12 ms 7000 KB Output is correct
10 Correct 12 ms 7516 KB Output is correct
11 Correct 11 ms 6492 KB Output is correct
12 Correct 12 ms 7256 KB Output is correct
13 Correct 12 ms 7260 KB Output is correct
14 Correct 13 ms 7260 KB Output is correct
15 Correct 14 ms 7736 KB Output is correct
16 Correct 0 ms 344 KB Output is correct
17 Execution timed out 4041 ms 8208 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 13 ms 8532 KB Output is correct
3 Correct 11 ms 7516 KB Output is correct
4 Correct 12 ms 8540 KB Output is correct
5 Correct 11 ms 7768 KB Output is correct
6 Correct 16 ms 8028 KB Output is correct
7 Correct 11 ms 6748 KB Output is correct
8 Correct 17 ms 7984 KB Output is correct
9 Correct 12 ms 7000 KB Output is correct
10 Correct 12 ms 7516 KB Output is correct
11 Correct 11 ms 6492 KB Output is correct
12 Correct 12 ms 7256 KB Output is correct
13 Correct 12 ms 7260 KB Output is correct
14 Correct 13 ms 7260 KB Output is correct
15 Correct 14 ms 7736 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Execution timed out 4086 ms 8908 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 2 ms 344 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 348 KB Output is correct
9 Correct 5 ms 504 KB Output is correct
10 Correct 2 ms 348 KB Output is correct
11 Correct 5 ms 348 KB Output is correct
12 Correct 2 ms 496 KB Output is correct
13 Correct 4 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 3 ms 504 KB Output is correct
16 Correct 4 ms 348 KB Output is correct
17 Correct 2 ms 344 KB Output is correct
18 Correct 5 ms 344 KB Output is correct
19 Correct 2 ms 348 KB Output is correct
20 Correct 10 ms 504 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 13 ms 8532 KB Output is correct
23 Correct 11 ms 7516 KB Output is correct
24 Correct 12 ms 8540 KB Output is correct
25 Correct 11 ms 7768 KB Output is correct
26 Correct 16 ms 8028 KB Output is correct
27 Correct 11 ms 6748 KB Output is correct
28 Correct 17 ms 7984 KB Output is correct
29 Correct 12 ms 7000 KB Output is correct
30 Correct 12 ms 7516 KB Output is correct
31 Correct 11 ms 6492 KB Output is correct
32 Correct 12 ms 7256 KB Output is correct
33 Correct 12 ms 7260 KB Output is correct
34 Correct 13 ms 7260 KB Output is correct
35 Correct 14 ms 7736 KB Output is correct
36 Correct 887 ms 8448 KB Output is correct
37 Correct 1295 ms 7420 KB Output is correct
38 Correct 1516 ms 8964 KB Output is correct
39 Correct 365 ms 9576 KB Output is correct
40 Correct 1636 ms 9124 KB Output is correct
41 Correct 1923 ms 9984 KB Output is correct
42 Correct 2509 ms 9444 KB Output is correct
43 Correct 1514 ms 8312 KB Output is correct
44 Correct 1836 ms 8428 KB Output is correct
45 Correct 782 ms 7252 KB Output is correct
46 Correct 1129 ms 7348 KB Output is correct
47 Correct 1488 ms 8328 KB Output is correct
48 Correct 614 ms 7168 KB Output is correct
49 Correct 2064 ms 7428 KB Output is correct
50 Correct 1079 ms 8960 KB Output is correct
51 Execution timed out 4075 ms 7760 KB Time limit exceeded
52 Halted 0 ms 0 KB -