제출 #570812

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
570812		knightron0	Simple game (IZhO17_game)	C++14	100 / 100	419 ms	43468 KiB

game

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

#define pb push_back
#define fr first
#define sc second
#define clr(a, x) memset(a, x, sizeof(a))
#define dbg(x) cout<<"("<<#x<<"): "<<x<<endl;
#define printvector(arr) for (auto it = arr.begin(); it != arr.end(); ++it) cout<<*it<<" "; cout<<endl;
#define all(v) v.begin(), v.end()
#define lcm(a, b) (a * b)/__gcd(a, b)
#define int long long int
#define printvecpairs(vec) for(auto it: vec) cout<<it.fr<<' '<<it.sc<<endl;
#define endl '\n'
#define float long double

const int MOD = 1e9 + 7;
const int INF = 2e15;
const int MAXN = 1e6 + 5;
const int MX = 1e6;

int tree[4*MAXN], a[MAXN], lazy[4*MAXN];

void push(int v, int l, int r){
    int m = (l+r)/2;
    lazy[2*v] += lazy[v];
    lazy[2*v + 1] += lazy[v];
    tree[2*v] += lazy[v]*(m-l+1);
    tree[(2*v)+1] += lazy[v] * (r-(m+1)+1);
    lazy[v] = 0;
}

int query(int curr, int start, int end, int l, int r){
    if(r < start or end < l) return 0;
    if(l <= start and end <= r) return tree[curr];
    push(curr, start, end);
    int mid = (start+end)/2;
    int p1 = query(2*curr, start, mid, l, r);
    int p2 = query(2*curr +1, mid+1, end, l, r);
    return p1+ p2;
}

void build(int curr, int start, int end){
    lazy[curr]= 0;
    if(start == end) {
        tree[curr] = a[start];
    } else {
        int mid = (start+end)/2;
        build(2*curr, start, mid);
        build(2*curr+1, mid+1, end);
        tree[curr] = tree[2*curr] +  tree[2*curr+1];
    }
}

void update(int curr, int start, int end, int lx, int rx, int v){
    if(start > rx || end < lx) return;
    if(lx <= start && end <= rx){
        tree[curr] += v*(end-start+1);
        lazy[curr] += v;
        return;
    }
    push(curr, start, end);
    int mid = (start+end)/2;
    update(curr*2, start, mid, lx, rx, v);
    update(curr*2+1, mid+1, end, lx, rx, v);
    tree[curr] = tree[2*curr] + tree[2*curr+1];
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    #ifdef LOCAL
    freopen("input.txt", "r", stdin);
    #endif
    int n, k;
    cin>>n>>k;
    clr(a, 0);
    int b[n+3];
    for(int i=1;i<=n;i++){
        cin>>b[i];
    }
    build(1, 1, MX+2);
    for(int i=2;i<=n;i++){
        update(1, 1, MX+2, min(b[i], b[i-1]), max(b[i], b[i-1]), 1);
    }
    while(k--){
        int t1;
        cin>>t1;
        if(t1 == 1){
            int idx, x;
            cin>>idx>>x;
            if(idx > 1){
                update(1, 1, MX+2, min(b[idx], b[idx-1]), max(b[idx], b[idx-1]), -1);
                update(1, 1, MX+2, min(x, b[idx-1]), max(x, b[idx-1]), 1);
            }
            if(idx < n){
                update(1, 1, MX+2, min(b[idx], b[idx+1]), max(b[idx], b[idx+1]), -1);
                update(1, 1, MX+2, min(x, b[idx+1]), max(x, b[idx+1]), 1);   
            }
            b[idx] = x;
        } else {
            int x;
            cin>>x;
            cout<<query(1, 1, MX+2, x, x)<<endl;
        }
    }
    return 0;
}

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