Submission #167036

#	Time	Username	Problem	Language	Result	Execution time	Memory
167036		hentai_lover	Simple game (IZhO17_game)	C++14	0 / 100	1101 ms	189536 KiB

game

#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)500000 + 10;
const ll oo = ll(1e9) + 10;

ll n, Q;
ll a[N], mp[N];

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

    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(v > N)cout << 1 / 0;

            //удалить старую пару
            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
*/

Compilation message (stderr)

game.cpp: In function 'int main()':
game.cpp:85:32: warning: division by zero [-Wdiv-by-zero]
             if(v > N)cout << 1 / 0;
                              ~~^~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 27
• Subtask 3: 0 / 51