Submission #682686

#	Time	Username	Problem	Language	Result	Execution time	Memory
682686		HamletPetrosyan	Simple game (IZhO17_game)	C++17	100 / 100	201 ms	19704 KiB

game

/// -- -- ---- --- -- --
/// 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 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51