oj.uz

Submission #1102865

# Submission time Handle Problem Language Result Execution time Memory
1102865 2024-10-19T05:34:26 Z Muhammet Simple game (IZhO17_game) C++17
100 / 100
 427 ms 34380 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 = 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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31568 KB Output is correct
2 Correct 11 ms 31740 KB Output is correct
3 Correct 11 ms 31676 KB Output is correct
4 Correct 11 ms 31568 KB Output is correct
5 Correct 11 ms 31568 KB Output is correct
6 Correct 11 ms 31568 KB Output is correct
7 Correct 11 ms 31568 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31568 KB Output is correct
2 Correct 11 ms 31740 KB Output is correct
3 Correct 11 ms 31676 KB Output is correct
4 Correct 11 ms 31568 KB Output is correct
5 Correct 11 ms 31568 KB Output is correct
6 Correct 11 ms 31568 KB Output is correct
7 Correct 11 ms 31568 KB Output is correct
8 Correct 282 ms 33352 KB Output is correct
9 Correct 311 ms 34124 KB Output is correct
10 Correct 304 ms 34380 KB Output is correct
11 Correct 238 ms 32792 KB Output is correct
12 Correct 297 ms 33916 KB Output is correct
13 Correct 374 ms 34124 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 31568 KB Output is correct
2 Correct 11 ms 31740 KB Output is correct
3 Correct 11 ms 31676 KB Output is correct
4 Correct 11 ms 31568 KB Output is correct
5 Correct 11 ms 31568 KB Output is correct
6 Correct 11 ms 31568 KB Output is correct
7 Correct 11 ms 31568 KB Output is correct
8 Correct 282 ms 33352 KB Output is correct
9 Correct 311 ms 34124 KB Output is correct
10 Correct 304 ms 34380 KB Output is correct
11 Correct 238 ms 32792 KB Output is correct
12 Correct 297 ms 33916 KB Output is correct
13 Correct 374 ms 34124 KB Output is correct
14 Correct 389 ms 34288 KB Output is correct
15 Correct 424 ms 34340 KB Output is correct
16 Correct 427 ms 34220 KB Output is correct
17 Correct 384 ms 34124 KB Output is correct
18 Correct 397 ms 34280 KB Output is correct