oj.uz

Submission #216507

# Submission time Handle Problem Language Result Execution time Memory
216507 2020-03-27T12:06:49 Z someone_aa Simple game (IZhO17_game) C++17
0 / 100
 5 ms 512 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*maxn];
int lazy[4*maxn];

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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -