oj.uz

Submission #169047

# Submission time Handle Problem Language Result Execution time Memory
169047 2019-12-18T05:46:06 Z tselmegkh Simple game (IZhO17_game) C++14
0 / 100
 28 ms 25212 KB 
#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
long long tree[8000050], h[N], lazy[8000050];

void update(int v, int l, int r, int ql, int qr, int del){
	if(ql > qr || l > r)return;
	if(lazy[v] != 0){
		tree[v] += lazy[v];
		if(l != r){
			lazy[2 * v] += lazy[v];
			lazy[2 * v + 1] += lazy[v];
		}
		lazy[v] = 0;
	}
	if(ql > r || qr < l)return;
	if(ql <= l && qr >= r){
		tree[v] += del;
		if(l != r){
			lazy[2 * v] += del;
			lazy[2 * v + 1] += del;
		}
		return;
	}
	int mid = (l + r) / 2;
	update(v * 2, l, mid, ql, qr, del);
	update(v * 2 + 1, mid + 1, r, ql, qr, del);
	tree[v] = tree[v * 2] + tree[v * 2 + 1];
}
long long query(int v, int l, int r, int ql, int qr){
	if(l > r)return 0;
	if(lazy[v] != 0){
		tree[v] += lazy[v];
		if(l != r){
			lazy[v * 2] += lazy[v];
			lazy[v * 2 + 1] += lazy[v];
		}
		lazy[v] = 0;
	}
	if(ql > r || qr < l)return 0;
	if(ql == l && qr == r){
		return tree[v];
	}
	int mid = (l + r) / 2;
	return query(v * 2, l, mid, ql, qr) + query(v * 2 + 1, mid + 1, r, ql, qr);
}
int main(){
	int n, q;
	cin >> n >> q;
	for(int i = 1; i <= n; i++){
		cin >> h[i];
		if(i > 1){
			update(1, 1, 4000020, min(h[i], h[i - 1]) + 1, max(h[i], h[i - 1]) - 1, 1);
		}
	}
	while(q--){
		int type;
		cin >> type;
		if(type == 1){
			int pos, val;
			cin >> pos >> val;
			if(pos > 1)update(1, 1, 4000020, min(h[pos - 1], h[pos]), max(h[pos - 1], h[pos]), -1), update(1, 1, 4000020, min((long long)val, h[pos - 1]) + 1, max((long long)val, h[pos - 1]) - 1, 1);
			if(pos < n)update(1, 1, 4000020, min(h[pos + 1], h[pos]), max(h[pos + 1], h[pos]), -1), update(1, 1, 4000020, min((long long)val, h[pos + 1]) + 1, max((long long)val, h[pos + 1]) - 1, 1);

		}else{
			int val;
			cin >> val;
			cout << query(1, 1, 4000020, val, val) << '\n';
		}
	}
}

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 28 ms 25212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 28 ms 25212 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Incorrect 28 ms 25212 KB Output isn't correct
3 Halted 0 ms 0 KB -