Submission #1122592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122592		I_love_Banu	Simple game (IZhO17_game)	C++20	100 / 100	187 ms	5232 KiB

game

#include"bits/stdc++.h"
using namespace std;
using ll=long long;
template<class T>using v=vector<T>;
using vi=v<int>;
#define sz(x) int(size(x))
#define all(x) begin(x),end(x)
#define rall(x) rbegin(x),rend(x)
#define lb lower_bound
#define ub upper_bound
template<class T>int lwb(v<T>&a,T b) {
    return int(lb(all(a),b)-begin(a));
}
template<class T>int lwb(T a[],int n,T b) {
    return int(lb(a,a+n,b)-a);
}
template<class T>int upb(v<T>&a,T b) {
    return int(ub(all(a),b)-begin(a));
}
template<class T>int upb(T a[],int n,T b) {
    return int(ub(a,a+n,b)-a);
}
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for(int i=(b)-1;(a)<=i;i--)
#define R0F(i,a) ROF(i,0,a)
#define rep(a) F0R(_,a)

const int mxN = 1e6+6;

struct fwtree {
    int ar[mxN];
    void add(int i, int x) {
        for (++ i; i < mxN; i += i & -i) {
            ar[i] += x;
        }
    }
    int qry(int i) {
        int ans = 0;
        for (++ i; i; i -= i & -i) {
            ans += ar[i];
        }
        return ans;
    }
} fw;

int h[mxN];

void erase(int i) {
    if (h[i + 1] < h[i]) {
        fw.add(h[i + 1] + 1, -1);
        fw.add(h[i], 1);
    } else if (h[i] < h[i + 1]) {
        fw.add(h[i] + 1, -1);
        fw.add(h[i + 1], 1);
    }
}

void add(int i) {
    if (h[i] < h[i + 1]) {
        fw.add(h[i] + 1, 1);
        fw.add(h[i + 1], -1);
    } else if (h[i + 1] < h[i]) {
        fw.add(h[i + 1] + 1, 1);
        fw.add(h[i], -1);
    }
}

main() {
    int N, M;
    cin >> N >> M;

    F0R(i, N) {
        cin >> h[i];
    }

    F0R(i, N - 1) {
        add(i);
    }

    rep(M) {
        int C;
        cin >> C;
        if (1 == C) {
            int i, x;
            cin >> i >> x;
            i --;
            if (0 < i)
                erase(i - 1);
            if (i < N - 1)
                erase(i);
            h[i] = x;
            if (0 < i)
                add(i - 1);
            if (i < N - 1)
                add(i);
        } else {
            int h;
            cin >> h;
            cout << fw.qry(h) << endl;
        }
    }
}

Compilation message (stderr)

game.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main() {
      | ^~~~

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