Submission #884563

#	Time	Username	Problem	Language	Result	Execution time	Memory
884563		tsumondai	Simple game (IZhO17_game)	C++14	100 / 100	243 ms	21308 KiB

game

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e9, mod = 1e9 + 7;
 
int n, m, k, a[N], q;

struct Node{
	int lazy;
	int val;
} nodes[N*4];

void down(int id) {
	int t=nodes[id].lazy;
	nodes[id*2].lazy+=t;
	nodes[id*2].val+=t;
	nodes[id*2+1].lazy+=t;
	nodes[id*2+1].val+=t;
	nodes[id].lazy=0;
}

void update(int id, int l, int r, int u, int v, int val) {
    if (v < l || r < u) {
        return;
    }
    if (u <= l && r <= v) {
        nodes[id].val += val;
        nodes[id].lazy += val;
        return;
    }
    int mid = (l + r) / 2;

    down(id); 

    update(id*2, l, mid, u, v, val);
    update(id*2+1, mid+1, r, u, v, val);

    nodes[id].val = (nodes[id*2].val+nodes[id*2+1].val);
}

int get(int id, int l, int r, int u, int v) {
	if (u>r || v<l /*|| l>r || u>v*/) return 0;
	if (l>=u && r<=v) return nodes[id].val;
	down(id);
	int mid=(l+r)/2;
	return (get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v));
}

void process() {
	cin >> n >> q;
	foru(i,1,n) cin >> a[i];
	foru(i,2,n) {
		int lo=min(a[i-1], a[i]);
		int hi=max(a[i-1], a[i]);
		update(1,1,N,lo,hi,1);
	}

	while (q--) {
		int type; cin >> type;
		if (type==1) {
			int pos, val; cin >> pos >> val;
			// update
			int lo, hi;
			if (pos==n) {
				lo=min(a[pos], a[pos-1]); 
				hi=max(a[pos-1], a[pos]);
				update(1,1,N,lo,hi,-1);
				a[pos]=val;
				lo=min(a[pos], a[pos-1]); 
				hi=max(a[pos-1], a[pos]);
				update(1,1,N,lo,hi,1);
				continue;
			}
			if (pos==1) {
				lo=min(a[pos], a[pos+1]); 
				hi=max(a[pos], a[pos+1]);
				update(1,1,N,lo,hi,-1);
				a[pos]=val;
				lo=min(a[pos], a[pos+1]); 
				hi=max(a[pos], a[pos+1]);
				update(1,1,N,lo,hi,1);
				continue;
			}
			// left
			int old=a[pos];
			lo=min(a[pos], a[pos-1]); 
			hi=max(a[pos], a[pos-1]);
			update(1,1,N,lo,hi,-1);
			a[pos]=val;
			lo=min(a[pos], a[pos-1]); 
			hi=max(a[pos], a[pos-1]);
			update(1,1,N,lo,hi,1);
			// right
			a[pos]=old;
			lo=min(a[pos], a[pos+1]); 
			hi=max(a[pos], a[pos+1]);
			update(1,1,N,lo,hi,-1);
			a[pos]=val;
			lo=min(a[pos], a[pos+1]); 
			hi=max(a[pos], a[pos+1]);
			update(1,1,N,lo,hi,1);
			continue;
		} else {
			int height; cin >> height;
			// query
			cout << get(1,1,N,height,height) << '\n';
		}
	}
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

// dont stop

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