Submission #877291

#	Time	Username	Problem	Language	Result	Execution time	Memory
877291		marcid	Simple game (IZhO17_game)	C++17	0 / 100	2 ms	2396 KiB

game

//izho17_2A
#include <bits/stdc++.h>
#define int long long
const int maxn = 1e5+1;
using namespace std;
int a[maxn], heights[maxn], f[maxn], tree[maxn<<2], n, m;
//int op(int u, int v) {
//    return ;
//}
/*int get(int v = 1, int tl = 1, int tr = n, int h) {
    if (l > tr || tl > r) return 0;
    if (l <= tl && tr <= r) return tree[v];
    int mid = tl+tr>>1;
    return get(v*2,tl,mid,h)+get(v*2+1,mid+1,tr,h);
}

void build(int v = 1, int tl = 1, int tr = n) {
    if (tl==tr) {
        tree[v]=a[tl]; return;
    } int mid = tl+tr>>1;
    build(v*2,tl,mid); build(v*2+1,mid+1,tr);
    tree[v]=op(tree[v*2],tree[v*2+1]);
    .
}*/

signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 2; i <= n; i++) {
        if (a[i]>a[i-1]) {
            for (int j = a[i-1]+1; j <= a[i]; j++) {
                heights[j]++;
            }
        } else {
            for (int j = a[i]+1; j <= a[i-1]; j++) {
                heights[j]++;
            }
        } if (i==2) heights[min(a[i],a[i-1])]=1;
    }
    //build();
    for (;m--;) {
        int k; cin >> k;
        if (k-1) {
            int c; cin >> c;
            cout << heights[c] << '\n';
        } else {
            int pos, val; cin >> pos >> val;
            if (pos==1 || pos == n) {
                if (pos==1) {
                    if (a[pos] < val) {
                        for (int j = a[pos]; j <= val; j++) {
                            heights[j]-=(j<a[pos+1]);
                            heights[j]+=(j>a[pos+1]);
                        }
                    } else {
                        for (int j = a[pos]; j >= val; j--) {
                            heights[j]-=(j>a[pos+1]);
                            heights[j]+=(j<a[pos+1]);
                        }
                    }
                } else {
                    if (a[pos] < val) {
                        for (int j = a[pos]; j<=val; j++) {
                            heights[j]-=(j<a[pos-1]);
                            heights[j]+=(j>a[pos-1]);
                        }
                    } else {
                        for (int j = a[pos]; j>=val; j--) {
                            heights[j]-=(j>a[pos-1]);
                            heights[j]+=(j<a[pos-1]);
                        }
                    }
                }
                continue;
            }
            if (a[pos] > val) {
                heights[val]--;
                for (int j = val; j < a[pos]; j++) {
                    heights[j]+=heights[val-1];
                } heights[a[pos]]++;
            } else {
                heights[a[pos]]--;
                for (int j = a[pos]; j < val; j++) {
                    heights[j]+=heights[a[pos]-1];
                } heights[val]++;
            }
        }
    }
}

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