제출 #780791

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
780791		PoPularPlusPlus	Simple game (IZhO17_game)	C++17	100 / 100	371 ms	19344 KiB

game

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

const int N = 1000002;

struct Seg{
    
    int siz;
    vector<int> v,lazy;
    
    void init(int n){
        siz = 1;
        while(siz < n)siz *= 2;
        
        v.assign(siz * 2 , 0);
        lazy.assign(siz*2,0);
    }
    
    void set(int l , int r , int val, int x , int lx , int rx){
        if(l >= rx || r <= lx)return;
        if(lx >= l && rx <= r){
            v[x] += val*(rx-lx);
            lazy[x]+=val;
            return;
        }
        lazy[2 * x + 1] += lazy[x];
        lazy[2 * x + 2] += lazy[x];
        int m = (lx + rx)/2;
        v[2*x+1]+=lazy[x]*(m-lx);
        v[2*x+2]+=lazy[x]*(rx-m);
        lazy[x] = 0;
        set(l,r,val,2*x+1,lx,m);
        set(l,r,val,2*x+2,m,rx);
        v[x]=v[2*x+1] + v[2*x+2];
    }
    
    void set(int l, int r , int val){
        set(l,r,val,0,0,siz);
    }
    
    int sum(int pos , int x, int lx , int rx){
        if(rx-lx==1)return v[x];
        lazy[2 * x + 1] += lazy[x];
        lazy[2 * x + 2] += lazy[x];
        int m = (lx + rx)/2;
        v[2*x+1]+=lazy[x]*(m-lx);
        v[2*x+2]+=lazy[x]*(rx-m);
        lazy[x] = 0;
        return (pos < m ? sum(pos,2*x+1,lx,m):sum(pos,2*x+2,m,rx));
    }
    
    int sum(int pos){
        return sum(pos,0,0,siz);
    }
};

void solve(){
    int n , m;
    cin >> n >> m;
    Seg st;
    st.init(N);
    int arr[n];
    for(int i = 0; i < n; i++){
        cin >> arr[i];
        if(i){
            st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,1);
        }
    }
    while(m--){
        int t;
        cin >> t;
        if(t==1){
            int i , val;
            cin >> i >> val;
            i--;
            if(i){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,-1);
            }
            i++;
            if(i < n){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,-1);
            }
            i--;
            arr[i] = val;
            if(i){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,1);
            }
            i++;
            if(i < n){
                st.set(min(arr[i],arr[i-1]),max(arr[i],arr[i-1])+1,1);
            }
        }
        else {
            int pos;
            cin>>pos;
            cout << st.sum(pos) << '\n';
        }
    }
}

int main() {
	// your code goes here
//	int t;
//	cin >> t;
//	while(t--){
	    solve();
//	}
	return 0;
}

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