oj.uz

Submission #167043

# Submission time Handle Problem Language Result Execution time Memory
167043 2019-12-05T10:47:48 Z hentai_lover Simple game (IZhO17_game) C++14
22 / 100
 813 ms 262148 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

//#define tree zalupa
#define fr(i, l, r) for(ll i = l; i <= r; ++ i)
#define rf(i, r, l) for(ll i = l; i >= r; -- i)

using namespace std;
using namespace __gnu_pbds;

template <typename T>
using _set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef int ll;
typedef pair<ll, ll> pll;

const ll N = (ll)1000000;
const ll oo = ll(1e9) + 10;

ll n, Q;
ll a[100100], mp[1000100];

struct SegmentTree{
    vector < _set < pair < int, int> > > t;
    void uni(){
        t.resize(2097162);
    }

    void del(ll x, ll y, ll z, ll v = 1, ll l = 1, ll r = N){
        if(l != r){
            ll c = (l + r) / 2;
            if(x <= c)del(x, y, z, v * 2, l, c);
            else del(x, y, z, v * 2 + 1, c + 1, r);
        }
        t[v].erase({y, z});
    }

    void ins(ll x, ll y, ll z, ll v = 1, ll l = 1, ll r = N){
        if(l != r){
            ll c = (l + r) / 2;
            if(x <= c)ins(x, y, z, v * 2, l, c);
            else ins(x, y, z, v * 2 + 1, c + 1, r);
        }
        t[v].insert({y, z});
    }

    ll get(ll l, ll r, ll x, ll v = 1, ll tl = 1, ll tr = N){
        if(l > r)return 0;
        if(tl == l && tr == r){
            pll p;
            p = make_pair(x, -oo);
            ll v1 = t[v].order_of_key(p);

            return t[v].size() - v1;
        }

        ll c = (tl + tr) / 2;
        return get(l, min(r, c), x, v * 2, tl, c) + get(max(l, c + 1), r, x, v * 2 + 1, c + 1, tr);
    }
} tree1488;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    tree1488.uni();
    cin >> n >> Q;
    fr(i, 1, n)cin >> a[i];
    a[0] = a[1];

    fr(i, 1, n){
        ll x = a[i - 1];
        ll y = a[i];
        if(x > y)swap(x, y);
        if(x == y)mp[x] ++;
        else tree1488.ins(x, y, i);
    }

    //cout << "kjfd" << endl;

    fr(z, 1, Q){
        ll t;
        cin >> t;
        if(t == 1){
            ll p, v;
            cin >> p >> v;

            //удалить старую пару
            if(p == 1 || a[p - 1] == a[p])mp[a[p]] --;
            else {
                ll x = a[p - 1], y = a[p];
                if(x > y)swap(x, y);


                tree1488.del(x, y, p);
            }

            if(p != n){
                if(a[p + 1] == a[p])mp[a[p]] --;
                else{
                    ll x = a[p + 1], y = a[p];
                    if(x > y)swap(x, y);

                    tree1488.del(x, y, p + 1);
                }
            }

            a[p] = v;
            //добавить новую пару

            if(p == 1 || a[p - 1] == a[p])mp[a[p]] ++;
            else {
                ll x = a[p - 1], y = a[p];
                if(x > y)swap(x, y);
                tree1488.ins(x, y, p);
            }

            if(p != n){
                if(a[p + 1] == a[p])mp[a[p]] ++;
                else{
                    ll x = a[p + 1], y = a[p];
                    if(x > y)swap(x, y);

                    tree1488.ins(x, y, p + 1);
                }
            }

        }   else{
            ll x, ans = 0;
            cin >> x;
            ans = tree1488.get(1, x, x);
            cout << ans << "\n";
        }
    }
}


/*
3 3
1 5 1
2 3
1 3 5
2 3
*/

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 197300 KB Output is correct
2 Correct 276 ms 198780 KB Output is correct
3 Correct 280 ms 198648 KB Output is correct
4 Correct 283 ms 198648 KB Output is correct
5 Correct 280 ms 198780 KB Output is correct
6 Correct 281 ms 198648 KB Output is correct
7 Correct 274 ms 198612 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 197300 KB Output is correct
2 Correct 276 ms 198780 KB Output is correct
3 Correct 280 ms 198648 KB Output is correct
4 Correct 283 ms 198648 KB Output is correct
5 Correct 280 ms 198780 KB Output is correct
6 Correct 281 ms 198648 KB Output is correct
7 Correct 274 ms 198612 KB Output is correct
8 Runtime error 813 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 197300 KB Output is correct
2 Correct 276 ms 198780 KB Output is correct
3 Correct 280 ms 198648 KB Output is correct
4 Correct 283 ms 198648 KB Output is correct
5 Correct 280 ms 198780 KB Output is correct
6 Correct 281 ms 198648 KB Output is correct
7 Correct 274 ms 198612 KB Output is correct
8 Runtime error 813 ms 262148 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Halted 0 ms 0 KB -