Submission #1182645

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182645		VMaksimoski008	Simple game (IZhO17_game)	C++20	100 / 100	34 ms	5192 KiB

game

#include <bits/stdc++.h>
#define ar array
//#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e18;
const int N = 1e6 + 5;

struct fenwick {
    int n;
    vector<int> tree;

    fenwick(int _n) : n(_n+10), tree(n+50) {}

    void update(int p, int v) {
        for(p++; p<n; p+=p&-p) tree[p] += v;
    }

    int query(int p) {
        int ans = 0;
        for(p++; p; p-=p&-p) ans += tree[p];
        return ans;
    }

    void update(int l, int r, int v) {
        if(l > r) swap(l, r);
        update(l, v);
        update(r+1, -v);
    }
} fwt(N);

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

    int n, q; cin >> n >> q;
    vector<int> a(n+1);
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=1; i<n; i++) fwt.update(a[i], a[i+1], 1);

    while(q--) {
        int t; cin >> t;
        if(t == 1) {
            int p, v; cin >> p >> v;

            if(p > 1) fwt.update(a[p-1], a[p], -1);
            if(p < n) fwt.update(a[p], a[p+1], -1);
            a[p] = v;
            if(p > 1) fwt.update(a[p-1], a[p], 1);
            if(p < n) fwt.update(a[p], a[p+1], 1);
        } else {
            int h; cin >> h;
            cout << fwt.query(h) << '\n';
        }
    }
}

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