oj.uz

Submission #170233

# Submission time Handle Problem Language Result Execution time Memory
170233 2019-12-24T09:58:19 Z theboatman Simple game (IZhO17_game) C++17
100 / 100
 99 ms 10540 KB 
#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.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 10 ms 8188 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 10 ms 8184 KB Output is correct
6 Correct 11 ms 8120 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 10 ms 8188 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 10 ms 8184 KB Output is correct
6 Correct 11 ms 8120 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 58 ms 9308 KB Output is correct
9 Correct 77 ms 10540 KB Output is correct
10 Correct 73 ms 10488 KB Output is correct
11 Correct 57 ms 9592 KB Output is correct
12 Correct 64 ms 10148 KB Output is correct
13 Correct 66 ms 10488 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 8184 KB Output is correct
2 Correct 9 ms 8184 KB Output is correct
3 Correct 10 ms 8188 KB Output is correct
4 Correct 9 ms 8184 KB Output is correct
5 Correct 10 ms 8184 KB Output is correct
6 Correct 11 ms 8120 KB Output is correct
7 Correct 9 ms 8184 KB Output is correct
8 Correct 58 ms 9308 KB Output is correct
9 Correct 77 ms 10540 KB Output is correct
10 Correct 73 ms 10488 KB Output is correct
11 Correct 57 ms 9592 KB Output is correct
12 Correct 64 ms 10148 KB Output is correct
13 Correct 66 ms 10488 KB Output is correct
14 Correct 96 ms 10232 KB Output is correct
15 Correct 99 ms 10192 KB Output is correct
16 Correct 99 ms 10236 KB Output is correct
17 Correct 94 ms 10204 KB Output is correct
18 Correct 97 ms 10104 KB Output is correct