oj.uz

Submission #170203

# Submission time Handle Problem Language Result Execution time Memory
170203 2019-12-24T08:32:54 Z theboatman Simple game (IZhO17_game) C++17
0 / 100
 1000 ms 39416 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 = 1e18 + 10;
const int inf = 1e9 + 10;
const int N = 1e5 + 10;

struct Tree {
    int v, tl, tr, timer;
    vector <ordset <pair <int, int> > > t;

    void init(int n) {
        v = 1;
        tl = 1;
        tr = n;

        timer = 0;
        t.resize(n * 4);
    }

    void add(int v, int tl, int tr, int pos, int val) {
        t[v].insert({val, timer++});

        if (tl == tr) {
            return;
        }

        int tm = tl + tr >> 1;
        if (pos <= tm) {
            add(v << 1, tl, tm, pos, val);
        }
        else {
            add(v << 1 | 1, tm + 1, tr, pos, val);
        }
    }

    void del(int v, int tl, int tr, int pos, int val) {
        t[v].erase(t[v].lower_bound({val, -inf}));

        if (tl == tr) {
            return;
        }

        int tm = tl + tr >> 1;
        if (pos <= tm) {
            del(v << 1, tl, tm, pos, val);
        }
        else {
            del(v << 1 | 1, tm + 1, tr, pos, val);
        }
    }

    int get(int v, int tl, int tr, int l, int r, int R) {
        if (l > r) {
            return 0;
        }

        if (tl == l && tr == r) {
            return t[v].size() - t[v].order_of_key({R + 1, -inf});
        }

        int tm = tl + tr >> 1;
        int ql = get(v << 1, tl, tm, l, min(r, tm), R);
        int qr = get(v << 1 | 1, tm + 1, tr, max(l, tm + 1), r, R);

        return ql + qr;
    }

    void add(int pos, int val) {
        add(v, tl, tr, pos, val);
    }

    void del(int pos, int val) {
        del(v, tl, tr, pos, val);
    }

    int get(int l, int r, int R) {
        return get(v, tl, tr, l, r, R);
    }
};

int main() {
    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 osu;
    osu.init(N);

    for(int i = 1; i < n; i++) {
        osu.add(min(a[i], a[i - 1]), max(a[i], a[i - 1]));
    }

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

    for(int iq = 0; iq < m; iq++) {
        int type;
        cin >> type;

        if (type == 2) {
            int x;
            cin >> x;

            cout << cnt[x] + osu.get(1, x - 1, x) << "\n";
        }
        else {
            int pos, val;
            cin >> pos >> val;
            pos--;

            if (pos > 0) {
                osu.del(min(a[pos], a[pos - 1]), max(a[pos], a[pos - 1]));
            }

            if (pos < n - 1) {
                osu.del(min(a[pos], a[pos + 1]), max(a[pos], a[pos + 1]));
            }

            a[pos] = val;

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

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

    return 0;
}

/*
*/

Compilation message

game.cpp: In member function 'void Tree::add(int, int, int, int, int)':
game.cpp:39:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int tm = tl + tr >> 1;
                  ~~~^~~~
game.cpp: In member function 'void Tree::del(int, int, int, int, int)':
game.cpp:55:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int tm = tl + tr >> 1;
                  ~~~^~~~
game.cpp: In member function 'int Tree::get(int, int, int, int, int, int)':
game.cpp:73:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int tm = tl + tr >> 1;
                  ~~~^~~~

Subtask #1
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 38364 KB Output is correct
2 Execution timed out 1084 ms 39416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 38364 KB Output is correct
2 Execution timed out 1084 ms 39416 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 38364 KB Output is correct
2 Execution timed out 1084 ms 39416 KB Time limit exceeded
3 Halted 0 ms 0 KB -