oj.uz

Submission #167057

# Submission time Handle Problem Language Result Execution time Memory
167057 2019-12-05T11:44:25 Z hentai_lover Simple game (IZhO17_game) C++14
22 / 100
 1000 ms 116128 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#pragma GCC optimize("-O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")

#define pb push_back
#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 oo = ll(1e9) + 10;

ll n, Q, N;
ll a[100100], mp[1000100], nmb[1000010], ans;

struct SegmentTree{
    vector < _set < pair < int, int> > > t;
    void uni(ll n){
        ll k = 1;
        while(k < n)k *= 2;
        t.resize(2 * k + 10);
    }

    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});
    }

    void get(ll l, ll r, ll x, ll v = 1, ll tl = 1, ll tr = N){
        if(l > r)return;
        if(tl == l && tr == r){
            ans += t[v].size() - t[v].order_of_key(make_pair(x, -oo));
            return;
        }

        ll c = (tl + tr) / 2;
        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);
    set <ll> st, s2;
    cin >> n >> Q;
    fr(i, 1, n){
        cin >> a[i];
        st.insert(a[i]);
    }

    struct dt{
        ll t, x, y;
    };
    vector <dt> q;
    fr(z, 1, Q){
        ll t;
        cin >> t;
        if(t == 1){
            ll p, v;
            cin >> p >> v;
            q.pb({t, p, v});
            st.insert(v);
        }   else{
            ll x;
            cin >> x;
            //s2.insert(x);
            q.pb({t, x, x});
        }
    }

    //сожмем координаты
    ll now = 1;
    for(auto i : st)nmb[i] = now ++;
    vector <ll> vv;
    for(auto i : st)vv.pb(i);
    now --;
    fr(i, 1, n)a[i] = nmb[a[i]];
    tree1488.uni(now);
    N = now;

    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);
    }
    for(auto i : q){
        ll t = i.t;
        if(t == 1){
            ll p = i.x;
            ll v = nmb[i.y];

            //удалить старую пару
            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{
            ans = 0;
            ll x = upper_bound(vv.begin(), vv.end(), i.x) - vv.begin(), y = x;
            if(x < vv.size()){
                if(vv[x] != i.x)y ++;
                tree1488.get(1, x, y);
            }
            cout << ans << "\n";
        }
    }
}


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

Compilation message

game.cpp: In function 'int main()':
game.cpp:157:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             if(x < vv.size()){
                ~~^~~~~~~~~~~

Subtask #1
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 4572 KB Output is correct
3 Correct 15 ms 4472 KB Output is correct
4 Correct 16 ms 4728 KB Output is correct
5 Correct 15 ms 4472 KB Output is correct
6 Correct 15 ms 4728 KB Output is correct
7 Correct 3 ms 504 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 4572 KB Output is correct
3 Correct 15 ms 4472 KB Output is correct
4 Correct 16 ms 4728 KB Output is correct
5 Correct 15 ms 4472 KB Output is correct
6 Correct 15 ms 4728 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 425 ms 31504 KB Output is correct
9 Execution timed out 1086 ms 116128 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 15 ms 4572 KB Output is correct
3 Correct 15 ms 4472 KB Output is correct
4 Correct 16 ms 4728 KB Output is correct
5 Correct 15 ms 4472 KB Output is correct
6 Correct 15 ms 4728 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 425 ms 31504 KB Output is correct
9 Execution timed out 1086 ms 116128 KB Time limit exceeded
10 Halted 0 ms 0 KB -