제출 #334678

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
334678		limabeans	Simple game (IZhO17_game)	C++17	100 / 100	438 ms	65772 KiB

game

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

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;

struct segtree {
    int n;
    vector<ll> t, o;
    void init(int _n) {
	n=_n+10;
	t.assign(4*n,0);
	o.assign(4*n,0);
    }

    void push(int v, int tl, int tr) {
	if (!o[v]) return;
	int tm=(tl+tr)/2;
	t[2*v] += 1ll*(tm-tl+1)*o[v];
	t[2*v+1] += 1ll*(tr-tm)*o[v];
	o[2*v] += o[v];
	o[2*v+1] += o[v];
	o[v] = 0;
    }

    ll qry(int v, int tl, int tr, int l, int r) {
	if (l>tr || r<tl) return 0;
	if (l<=tl && tr<=r) return t[v];
	push(v,tl,tr);
	int tm=(tl+tr)/2;
	return qry(2*v,tl,tm,l,r)+qry(2*v+1,tm+1,tr,l,r);
    }

    void upd(int v, int tl, int tr, int l, int r, ll dx) {
	if (l>tr || r<tl) return;
	if (l<=tl && tr<=r) {
	    t[v] += 1ll*(tr-tl+1)*dx;
	    o[v] += dx;
	} else {
	    push(v,tl,tr);
	    int tm=(tl+tr)/2;
	    upd(2*v,tl,tm,l,r,dx);
	    upd(2*v+1,tm+1,tr,l,r,dx);
	    t[v]=t[2*v]+t[2*v+1];
	}
    }
};

int n,q;
int a[maxn];

const int N = 1e6 + 10;
segtree tree;


void upd(int l, int r, int dx) {
    tree.upd(1,1,N,l,r,dx);
}

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

    cin>>n>>q;
    tree.init(N);

    for (int i=1; i<=n; i++) {
	cin>>a[i];
    }
    for (int i=1; i<n; i++) {
	int x = min(a[i],a[i+1]);
	int y = max(a[i],a[i+1]);
	upd(x,y,+1);
    }

    while (q--) {
	int op;
	cin>>op;
	if (op==1) {
	    int i,x;
	    cin>>i>>x;
	    if (i+1<=n) {
		upd(min(a[i],a[i+1]),max(a[i],a[i+1]),-1);
	    }
	    if (i-1>=1) {
		upd(min(a[i],a[i-1]),max(a[i],a[i-1]),-1);
	    }
	    a[i]=x;
	    if (i+1<=n) {
		upd(min(a[i],a[i+1]),max(a[i],a[i+1]),+1);
	    }
	    if (i-1>=1) {
		upd(min(a[i],a[i-1]),max(a[i],a[i-1]),+1);
	    }
	} else {
	    int h;
	    cin>>h;
	    cout<<tree.qry(1,1,N,h,h)<<"\n";
	}
    }
    
    
    
    return 0;
}

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