Submission #170233

#	Time	Username	Problem	Language	Result	Execution time	Memory
170233		theboatman	Simple game (IZhO17_game)	C++17	100 / 100	99 ms	10540 KiB

game

#include <bits/stdc++.h>

#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/assoc_container.hpp>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
template <typename T> using ordset = tree <T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const long long INF = ll(1e18) + 10;
const int inf = int(1e9) + 10;
const int N = int(1e6) + 10;

struct Tree {
    int n, timer;
    vector <int> t, t1;

    void init(int _n) {
        n = _n;
        timer = 0;

        t.resize(n + 1);
    }

    void add(int pos, int delta) {
        for(int i = pos; i <= n; i += i & -i) {
            t[i] += delta;
        }
    }

    int get(int pos) {
        int res = 0;
        for(int i = pos; i > 0; i -= i & -i) {
            res += t[i];
        }

        return res;
    }

    int get(int l, int r) {
        return get(r) - get(l - 1);
    }
};

void brute() {
    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    while(m--) {
        int type;
        cin >> type;

        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--;

            a[pos] = val;
        }
        else {
            int x;
            cin >> x;

            int ans = 0;
            for(auto i : a) {
                if (i == x) {
                    ans++;
                }
            }

            for(int i = 1; i < n; i++) {
                int l = min(a[i], a[i - 1]);
                int r = max(a[i], a[i - 1]);

                if (l < x && x < r) {
                    ans++;
                }
            }

            cout << ans << "\n";
        }
    }
}

int main() {
    //freopen("game.in", "r", stdin);
    //freopen("game.out", "w", stdout);

    cin.tie(0);
    ios::sync_with_stdio(0);

    int n, m;
    cin >> n >> m;

    vector <int> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    Tree osuL, osuR;
    osuL.init(N);
    osuR.init(N);

    for(int i = 1; i < n; i++) {
        int l = min(a[i], a[i - 1]);
        int r = max(a[i], a[i - 1]);

        osuL.add(l, 1);
        osuR.add(r, 1);
    }

    while(m--) {
        int type;
        cin >> type;

        if (type == 1) {
            int pos, val;
            cin >> pos >> val;
            pos--;

            if (pos > 0) {
                osuL.add(min(a[pos], a[pos - 1]), -1);
                osuR.add(max(a[pos], a[pos - 1]), -1);
            }

            if (pos < n - 1) {
                osuL.add(min(a[pos], a[pos + 1]), -1);
                osuR.add(max(a[pos], a[pos + 1]), -1);

            }

            a[pos] = val;

            if (pos > 0) {
                osuL.add(min(a[pos], a[pos - 1]), 1);
                osuR.add(max(a[pos], a[pos - 1]), 1);
            }

            if (pos < n - 1) {
                osuL.add(min(a[pos], a[pos + 1]), 1);
                osuR.add(max(a[pos], a[pos + 1]), 1);

            }
        }
        else {
            int x;
            cin >> x;

            int ans = n - 1;
            ans -= osuR.get(1, x);
            ans -= osuL.get(x, N);

            cout << ans << "\n";
        }
    }

    return 0;
}

/*
*/

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