oj.uz

Submission #216512

# Submission time Handle Problem Language Result Execution time Memory
216512 2020-03-27T12:12:10 Z someone_aa Simple game (IZhO17_game) C++17
100 / 100
 366 ms 19492 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define mp make_pair
using namespace std;

const int maxc = 1000100;
const int maxn = 100100;

int tree[4*maxc];
int lazy[4*maxc];

int n, q, arr[maxn];

void push_update(int li, int ri, int index) {
	if(lazy[index] != 0) {
		tree[index] += lazy[index] * (ri - li + 1);

		if(li != ri) {
			lazy[2*index] += lazy[index];
			lazy[2*index+1] += lazy[index];
		}
		lazy[index] = 0;
	}
}

void update(int ul, int ur, int uval, int li=0, int ri=maxc-1, int index=1) {
	push_update(li, ri, index);
	if(ul > ur) return;

	if(li > ur || ri < ul) return;
	else if(li >= ul && ri <= ur) {
		lazy[index] += uval;
		push_update(li, ri, index);
	}
	else {
		int mid = (li + ri) / 2;
		update(ul, ur, uval, li, mid, 2*index);
		update(ul, ur, uval, mid+1, ri, 2*index+1);

		tree[index] = tree[2*index] + tree[2*index+1];
	}
}

int query(int qind, int li=0, int ri=maxc-1, int index=1) {
	push_update(li, ri, index);

	if(li == ri) return tree[index];
	else {
		int mid = (li + ri) / 2;

		if(qind <= mid) return query(qind, li, mid, 2*index);
		else return query(qind, mid+1, ri, 2*index+1);
	}
}

void removeindex(int i) {
	if(i == 1 || i > n) return;

	if(abs(arr[i] - arr[i-1]) <= 1) return;

	if(arr[i-1] > arr[i]) {
		update(arr[i]+1, arr[i-1]-1, -1);
	}
	else {
		update(arr[i-1]+1, arr[i]-1, -1);
	}
}

void addindex(int i) {
	if(i == 1 || i > n) return;

	if(abs(arr[i] - arr[i-1]) <= 1) return;

	if(arr[i-1] > arr[i]) {
		update(arr[i]+1, arr[i-1]-1, 1);
	}
	else {
		update(arr[i-1]+1, arr[i]-1, 1);
	}
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);

	cin>>n>>q;
	for(int i=1;i<=n;i++) {
		cin>>arr[i];
		if(i > 1) {
			if(abs(arr[i] - arr[i-1]) <= 1) continue;

			if(arr[i-1] > arr[i]) {
				update(arr[i]+1, arr[i-1]-1, 1);
			}
			else {
				update(arr[i-1]+1, arr[i]-1, 1);
			}
		}
	}

	int qtype;
	while(q--) {
		cin>>qtype;

		int ind, val;
		if(qtype == 2) {
			cin>>ind;
			cout<<query(ind)<<"\n";
		}
		else {
			cin>>ind>>val;
			removeindex(ind);
			removeindex(ind+1);

			arr[ind] = val;
			addindex(ind);
			addindex(ind+1);
		}
	}
}

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 14 ms 14976 KB Output is correct
3 Correct 14 ms 14720 KB Output is correct
4 Correct 14 ms 14976 KB Output is correct
5 Correct 14 ms 14976 KB Output is correct
6 Correct 14 ms 14976 KB Output is correct
7 Correct 11 ms 12800 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 14 ms 14976 KB Output is correct
3 Correct 14 ms 14720 KB Output is correct
4 Correct 14 ms 14976 KB Output is correct
5 Correct 14 ms 14976 KB Output is correct
6 Correct 14 ms 14976 KB Output is correct
7 Correct 11 ms 12800 KB Output is correct
8 Correct 68 ms 1916 KB Output is correct
9 Correct 179 ms 19448 KB Output is correct
10 Correct 186 ms 19492 KB Output is correct
11 Correct 36 ms 1656 KB Output is correct
12 Correct 113 ms 3296 KB Output is correct
13 Correct 139 ms 19192 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 384 KB Output is correct
2 Correct 14 ms 14976 KB Output is correct
3 Correct 14 ms 14720 KB Output is correct
4 Correct 14 ms 14976 KB Output is correct
5 Correct 14 ms 14976 KB Output is correct
6 Correct 14 ms 14976 KB Output is correct
7 Correct 11 ms 12800 KB Output is correct
8 Correct 68 ms 1916 KB Output is correct
9 Correct 179 ms 19448 KB Output is correct
10 Correct 186 ms 19492 KB Output is correct
11 Correct 36 ms 1656 KB Output is correct
12 Correct 113 ms 3296 KB Output is correct
13 Correct 139 ms 19192 KB Output is correct
14 Correct 349 ms 19424 KB Output is correct
15 Correct 366 ms 19448 KB Output is correct
16 Correct 360 ms 19448 KB Output is correct
17 Correct 347 ms 19448 KB Output is correct
18 Correct 349 ms 19448 KB Output is correct