oj.uz

Submission #1102864

# Submission time Handle Problem Language Result Execution time Memory
1102864 2024-10-19T05:31:23 Z Muhammet Simple game (IZhO17_game) C++17
0 / 100
 16 ms 31580 KB 
#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 = 0;
	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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31568 KB Output is correct
2 Correct 12 ms 31568 KB Output is correct
3 Correct 15 ms 31568 KB Output is correct
4 Incorrect 16 ms 31580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31568 KB Output is correct
2 Correct 12 ms 31568 KB Output is correct
3 Correct 15 ms 31568 KB Output is correct
4 Incorrect 16 ms 31580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 31568 KB Output is correct
2 Correct 12 ms 31568 KB Output is correct
3 Correct 15 ms 31568 KB Output is correct
4 Incorrect 16 ms 31580 KB Output isn't correct
5 Halted 0 ms 0 KB -