제출 #169044

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
169044		tselmegkh	Simple game (IZhO17_game)	C++14	0 / 100	6 ms	1656 KiB

game

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 5;
int tree[N * 50], h[N], lazy[N * 50];

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];
}
int 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, N * 40, 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, N * 40, min(h[pos - 1], h[pos]), max(h[pos - 1], h[pos]), -1), update(1, 1, N * 10, min(val, h[pos - 1]) + 1, max(val, h[pos - 1]) - 1, 1);
			if(pos < n)update(1, 1, N * 40, min(h[pos + 1], h[pos]), max(h[pos + 1], h[pos]), -1), update(1, 1, N * 10, min(val, h[pos + 1]) + 1, max(val, h[pos + 1]) - 1, 1);

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

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51