oj.uz

Submission #682686

# Submission time Handle Problem Language Result Execution time Memory
682686 2023-01-16T19:05:31 Z HamletPetrosyan Simple game (IZhO17_game) C++17
100 / 100
 201 ms 19704 KB 
/// -- -- ---- --- -- --
/// 16.01.2023 Mon 23:05
/// -- -- ---- --- -- --

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

#define pll pair<long long, long long>
#define all(a) (a).begin(), (a).end()
#define len(a) ((int)(a).size())
#define add push_back
#define mkp make_pair
#define ll long long
#define fr first
#define sc second

const long long INF = 1000000000ll * 1000000003ll;
const long long MOD = 1000000007ll;
const long long N = 1e5 + 5, M = 1e6;

ll n, m, h[N];
ll t[4 * M + 5];

void update(ll v, ll tl, ll tr, ll ind, ll val){
	if(tl == tr){
		t[v] += val;
		return;
	}
	ll tm = (tl + tr) / 2;
	if(ind <= tm) update(2 * v + 0, tl, tm + 0, ind, val);
	else 		  update(2 * v + 1, tm + 1, tr, ind, val);
	t[v] = t[2 * v + 0] + t[2 * v + 1];
}

ll get(ll v, ll tl, ll tr, ll l, ll r){
	if(tl == l && tr == r) return t[v];
	ll tm = (tl + tr) / 2;
	if(r <= tm) return get(2 * v + 0, tl, tm + 0, l, r);
	if(l >  tm) return get(2 * v + 1, tm + 1, tr, l, r);
	return get(2 * v + 0, tl, tm + 0, l, tm + 0) +
		   get(2 * v + 1, tm + 1, tr, tm + 1, r);
}

void solve(){
	cin >> n >> m;
	for(int i = 1; i <= n; i++){
		cin >> h[i];
		if(i > 1){
			update(1, 1, M, min(h[i - 1], h[i]), +1);
			update(1, 1, M, max(h[i - 1], h[i]), -1);
		}
	}
	ll id, x, y;
	while(m--){
		cin >> id;
		if(id == 1){
			cin >> x >> y;
			if(x > 1){
				update(1, 1, M, min(h[x - 1], h[x]), -1);
				update(1, 1, M, max(h[x - 1], h[x]), +1);
			}
			if(x < n){
				update(1, 1, M, min(h[x + 1], h[x]), -1);
				update(1, 1, M, max(h[x + 1], h[x]), +1);
			}
			h[x] = y;
			if(x > 1){
				update(1, 1, M, min(h[x - 1], h[x]), +1);
				update(1, 1, M, max(h[x - 1], h[x]), -1);
			}
			if(x < n){
				update(1, 1, M, min(h[x + 1], h[x]), +1);
				update(1, 1, M, max(h[x + 1], h[x]), -1);
			}
		}
		else {
			cin >> x;
			cout << get(1, 1, M, 1, x) << "\n";
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	int _ = 1;
	// cout << fixed;
	// cout.precision(9);

	// cin >> _ ;
	while(_--) solve();
	return 0;
}

/// ---- - --------  ------ -------- -- - - -
/// just a reminder. ubuntu password is i o i
/// ---- - --------  ------ -------- -- - - -

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 11732 KB Output is correct
3 Correct 6 ms 11348 KB Output is correct
4 Correct 6 ms 11476 KB Output is correct
5 Correct 7 ms 11476 KB Output is correct
6 Correct 7 ms 11604 KB Output is correct
7 Correct 2 ms 336 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 11732 KB Output is correct
3 Correct 6 ms 11348 KB Output is correct
4 Correct 6 ms 11476 KB Output is correct
5 Correct 7 ms 11476 KB Output is correct
6 Correct 7 ms 11604 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 50 ms 2140 KB Output is correct
9 Correct 95 ms 19632 KB Output is correct
10 Correct 96 ms 19656 KB Output is correct
11 Correct 45 ms 1996 KB Output is correct
12 Correct 79 ms 3556 KB Output is correct
13 Correct 67 ms 3176 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 8 ms 11732 KB Output is correct
3 Correct 6 ms 11348 KB Output is correct
4 Correct 6 ms 11476 KB Output is correct
5 Correct 7 ms 11476 KB Output is correct
6 Correct 7 ms 11604 KB Output is correct
7 Correct 2 ms 336 KB Output is correct
8 Correct 50 ms 2140 KB Output is correct
9 Correct 95 ms 19632 KB Output is correct
10 Correct 96 ms 19656 KB Output is correct
11 Correct 45 ms 1996 KB Output is correct
12 Correct 79 ms 3556 KB Output is correct
13 Correct 67 ms 3176 KB Output is correct
14 Correct 171 ms 19632 KB Output is correct
15 Correct 186 ms 19704 KB Output is correct
16 Correct 181 ms 19688 KB Output is correct
17 Correct 178 ms 19616 KB Output is correct
18 Correct 201 ms 19624 KB Output is correct