Submission #883465

#	Time	Username	Problem	Language	Result	Execution time	Memory
883465		NintsiChkhaidze	Simple game (IZhO17_game)	C++17	100 / 100	224 ms	20052 KiB

game

#include <bits/stdc++.h>
#define pb push_back
#define s second
#define f first
#define left (h<<1),l,(l + r)/2
#define right ((h<<1)|1),(l + r)/2 + 1,r
#define pii pair<int,int>
#define ll long long 
#define int ll //?
using namespace std;

const int N = 1e5 + 5;

int a[N],t[4000005],n;

void updd(int h,int l,int r,int L,int R,int val){
	if (r < L || R < l) return;
	if (L <= l && r <= R){
		t[h] += val;
		return;
	}

	updd(left,L,R,val);
	updd(right,L,R,val);
}

int get(int h,int l,int r,int idx){
	if (l == r) return t[h];
	if (idx > (l + r)/2) return t[h] + get(right,idx);
	return t[h] + get(left,idx);
}

void upd(int k,int dl){
	int l = k - 1,r = k;
	if (l < 1 || r > n) return;

	int x = a[l],y = a[r];
	if (x > y) swap(x,y);
	updd(1,1,1000000,x,y,dl);
}

signed main (){
    ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);
	
	int q;
	cin>>n>>q;

	for (int i = 1; i <= n; i++){
		cin >> a[i];
		if (i > 1) upd(i,1);
	}

	while (q--){
		int tp;
		cin>>tp;
		if (tp == 1){
			int idx,val;
			cin>>idx>>val;

			upd(idx,-1);
			upd(idx+1,-1);

			a[idx] = val;

			upd(idx,1);
			upd(idx+1,1);
		}else{
			int x;
			cin>>x;
			cout<<get(1,1,1000000,x)<<endl;
		}
	}

}

• Subtask 1: 22 / 22
• Subtask 2: 27 / 27
• Subtask 3: 51 / 51