oj.uz

Submission #1102857

# Submission time Handle Problem Language Result Execution time Memory
1102857 2024-10-19T05:16:49 Z Muhammet Simple game (IZhO17_game) C++17
0 / 100
 15 ms 62800 KB 
#include <bits/stdc++.h>

using namespace std;

#define int long long

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);
	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(mx*4,0);
	lz.assign(mx*4,0);
	for(int i = 2; i <= n; i++){
		if(a[i-1]+1 <= a[i]-1){
			upd(1,1,mx,a[i-1]+1,a[i]-1,1);
		}
		else if(a[i]+1 <= a[i-1]-1){
			upd(1,1,mx,a[i]+1,a[i-1]-1,1);
		}
	}
	for(int i = 1; i <= m; i++){
		int t;
		cin >> t;
		if(t == 1){
			int ind, vl;
			cin >> ind >> vl;
			if(ind > 1){
				if(a[ind-1] + 1 <= a[ind] - 1){
					upd(1,1,mx,a[ind-1]+1,a[ind]-1,-1);
				}
				else if(a[ind] + 1 <= a[ind-1] - 1){
					upd(1,1,mx,a[ind]+1,a[ind-1]-1,-1);
				}
			}
			if(ind < n){
				if(a[ind] + 1 <= a[ind+1] - 1){
					upd(1,1,mx,a[ind]+1,a[ind+1]-1,-1);
				}
				else if(a[ind+1] + 1 <= a[ind] - 1){
					upd(1,1,mx,a[ind+1]+1,a[ind]-1,-1);
				}
			}
			a[ind] = vl;
			if(ind > 1){
				if(a[ind-1] + 1 <= a[ind] - 1){
					upd(1,1,mx,a[ind-1]+1,a[ind]-1,1);
				}
				else if(a[ind] + 1 <= a[ind-1] - 1){
					upd(1,1,mx,a[ind]+1,a[ind-1]-1,1);
				}
			}
			if(ind < n){
				if(a[ind] + 1 <= a[ind+1] - 1){
					upd(1,1,mx,a[ind]+1,a[ind+1]-1,1);
				}
				else if(a[ind+1] + 1 <= a[ind] - 1){
					upd(1,1,mx,a[ind+1]+1,a[ind]-1,1);
				}
			}
		}
		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 1 ms 336 KB Output is correct
2 Correct 15 ms 62800 KB Output is correct
3 Correct 14 ms 62800 KB Output is correct
4 Incorrect 15 ms 62800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 15 ms 62800 KB Output is correct
3 Correct 14 ms 62800 KB Output is correct
4 Incorrect 15 ms 62800 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 15 ms 62800 KB Output is correct
3 Correct 14 ms 62800 KB Output is correct
4 Incorrect 15 ms 62800 KB Output isn't correct
5 Halted 0 ms 0 KB -