Submission #1102865

#	Time	Username	Problem	Language	Result	Execution time	Memory
1102865		Muhammet	Simple game (IZhO17_game)	C++17	100 / 100	427 ms	34380 KiB

game

#include <bits/stdc++.h>

using namespace std;

int n, m, ans;

vector <int> st, lz;

void f(int nd, int l, int r){
	st[nd] += ((r-l+1) * (lz[nd]));
	if(l != r){
		lz[nd*2] += lz[nd];
		lz[nd*2+1] += lz[nd];
	}
	lz[nd] = 0;
	return;
}

int upd(int nd, int l, int r, int x, int y, int vl){
	f(nd,l,r);
	// cout << l << " " << r << " " << st[nd] << '\n';
	if(l > y or r < x) return st[nd];
	if(l >= x and r <= y){
		lz[nd] += vl;
		f(nd,l,r);
		return st[nd];
	}
	int md = (l + r) / 2;
	return st[nd] = (upd(nd*2,l,md,x,y,vl) + upd(nd*2+1,md+1,r,x,y,vl));
}

int fnd(int nd, int l, int r, int ind){
	f(nd,l,r);
	if((r < ind) or (l > ind)) return st[nd];
	if(l == r) {
		ans = st[nd];
		return st[nd];
	}
	int md = (l + r) / 2;
	return st[nd] = (fnd(nd*2,l,md,ind) + fnd(nd*2+1,md+1,r,ind));
}

signed main(){
	cin >> n >> m;
	vector <int> a(n+1);
	int mx = 1e6;
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		mx = max(mx,a[i]);
	}
	st.assign(4e6,0);
	lz.assign(4e6,0);
	for(int i = 2; i <= n; i++){
		if(min(a[i-1],a[i])+1 <= max(a[i-1],a[i])-1){
			upd(1,1,mx,min(a[i-1],a[i])+1,max(a[i-1],a[i])-1,1);
			// cout << '\n';
		}
	}
	for(int i = 1; i <= m; i++){
		int t;
		cin >> t;
		if(t == 1){
			int ind, vl;
			cin >> ind >> vl;
			mx = max(mx,vl);
			if(ind > 1){
				if(min(a[ind-1],a[ind]) + 1 <= max(a[ind-1],a[ind]) - 1){
					upd(1,1,mx,min(a[ind-1],a[ind])+1,max(a[ind-1],a[ind])-1,(-1));
					// cout << '\n';
				}
			}
			if(ind < n){
				if(min(a[ind],a[ind+1]) + 1 <= max(a[ind],a[ind+1]) - 1){
					upd(1,1,mx,min(a[ind],a[ind+1])+1,max(a[ind],a[ind+1])-1,(-1));
					// cout << '\n';
				}
			}
			a[ind] = vl;
			if(ind > 1){
				if(min(a[ind-1],a[ind]) + 1 <= max(a[ind-1],a[ind]) - 1){
					upd(1,1,mx,min(a[ind-1],a[ind])+1,max(a[ind-1],a[ind])-1,1);
					// cout << '\n';
				}
			}
			if(ind < n){
				if(min(a[ind],a[ind+1]) + 1 <= max(a[ind],a[ind+1]) - 1){
					upd(1,1,mx,min(a[ind],a[ind+1])+1,max(a[ind],a[ind+1])-1,1);
					// cout << '\n';
				}
			}
		}
		else {
			int x;
			cin >> x;
			ans = 0;
			fnd(1,1,mx,x);
			cout << ans << '\n';
		}
	}
}

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