oj.uz

Submission #167081

# Submission time Handle Problem Language Result Execution time Memory
167081 2019-12-05T13:28:07 Z hentai_lover Simple game (IZhO17_game) C++14
22 / 100
 1000 ms 79104 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){
        t.resize(n + 10);
    }

    void del(ll x, ll y, ll z){
        for(ll i = x; i <= N; i += i & -i)t[i].erase({y, z});
    }
    void ins(ll x, ll y, ll z){
        for(ll i = x; i <= N; i += i & -i)t[i].insert({y, z});
    }
    ll get(ll x, ll y){
        ll ans = 0;
        for(ll i = x; i >= 1; i -= i & -i)ans += t[i].size() - t[i].order_of_key(make_pair(y, -oo));
        return ans;
    }
} 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 ++;
                cout << tree1488.get(x, y);
            }   else cout << 0;

            cout << "\n";
        }
    }
}


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

Compilation message

game.cpp: In function 'int main()':
game.cpp:137: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 10 ms 4088 KB Output is correct
3 Correct 10 ms 3960 KB Output is correct
4 Correct 10 ms 3832 KB Output is correct
5 Correct 10 ms 3960 KB Output is correct
6 Correct 10 ms 4216 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 10 ms 4088 KB Output is correct
3 Correct 10 ms 3960 KB Output is correct
4 Correct 10 ms 3832 KB Output is correct
5 Correct 10 ms 3960 KB Output is correct
6 Correct 10 ms 4216 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 274 ms 23112 KB Output is correct
9 Execution timed out 1069 ms 79104 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 10 ms 4088 KB Output is correct
3 Correct 10 ms 3960 KB Output is correct
4 Correct 10 ms 3832 KB Output is correct
5 Correct 10 ms 3960 KB Output is correct
6 Correct 10 ms 4216 KB Output is correct
7 Correct 3 ms 504 KB Output is correct
8 Correct 274 ms 23112 KB Output is correct
9 Execution timed out 1069 ms 79104 KB Time limit exceeded
10 Halted 0 ms 0 KB -