oj.uz

Submission #794246

# Submission time Handle Problem Language Result Execution time Memory
794246 2023-07-26T11:24:15 Z sumit_kk10 Simple game (IZhO17_game) C++17
100 / 100
 369 ms 15852 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define fast ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
#define int long long
#define F first
#define S second
#define pb push_back
using namespace std;
#define ordered_set tree<pair<int, int>, null_type,less<pair<int, int> > , rb_tree_tag,tree_order_statistics_node_update>
const int N = 1e6 + 5, MOD = 1e9 + 7;
int n, q, a[N];

void solve(){
	cin >> n >> q;
	for(int i = 1; i <= n; ++i)
		cin >> a[i];
	ordered_set mx, mn;
	for(int i = 2; i <= n; ++i)
		mx.insert({max(a[i], a[i - 1]), i});
	for(int i = 2; i <= n; ++i)
		mn.insert({min(a[i], a[i - 1]), i});
	while(q--){
		int t;
		cin >> t;
		if(t == 1){
			int i, x;
			cin >> i >> x;
			if(i + 1 <= n){
				auto p = mx.find({max(a[i], a[i + 1]), i + 1});
				mx.erase(p);
				p = mn.find({min(a[i], a[i + 1]), i + 1});
				mn.erase(p);
			}
			if(i - 1 >= 1){
				auto p = mx.find({max(a[i], a[i - 1]), i});
				mx.erase(p);
				p = mn.find({min(a[i], a[i - 1]), i});
				mn.erase(p);
			}
			a[i] = x;
			if(i + 1 <= n){
				mx.insert({max(a[i], a[i + 1]), i + 1});
				mn.insert({min(a[i], a[i + 1]), i + 1});
			}
			if(i - 1 >= 1){
				mx.insert({max(a[i], a[i - 1]), i});
				mn.insert({min(a[i], a[i - 1]), i});
			}
		}
		else{
			int k;
			cin >> k;
			int ans = mx.size() - mx.order_of_key({k, 0});
			ans -= mn.size() - mn.order_of_key({k, 0});
			cout << ans << "\n";
		}
	}
}

int32_t main(){
	fast;
	int t = 1;
	// cin >> t;
	while(t--)
		solve();
	return 0;
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 484 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 484 KB Output is correct
8 Correct 96 ms 14520 KB Output is correct
9 Correct 177 ms 15764 KB Output is correct
10 Correct 162 ms 15832 KB Output is correct
11 Correct 85 ms 14416 KB Output is correct
12 Correct 125 ms 15540 KB Output is correct
13 Correct 197 ms 15608 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 1 ms 484 KB Output is correct
8 Correct 96 ms 14520 KB Output is correct
9 Correct 177 ms 15764 KB Output is correct
10 Correct 162 ms 15832 KB Output is correct
11 Correct 85 ms 14416 KB Output is correct
12 Correct 125 ms 15540 KB Output is correct
13 Correct 197 ms 15608 KB Output is correct
14 Correct 311 ms 15768 KB Output is correct
15 Correct 358 ms 15780 KB Output is correct
16 Correct 369 ms 15852 KB Output is correct
17 Correct 338 ms 15788 KB Output is correct
18 Correct 361 ms 15776 KB Output is correct