Submission #154871

#	Time	Username	Problem	Language	Result	Execution time	Memory
154871		hentai_lover	Segments (IZhO18_segments)	C++14	0 / 100	275 ms	65540 KiB

segments

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define lft(x) x * 2
#define rgt(x) x * 2 + 1

#define tm hui_pizda
#define ft first
#define sd second
#define pb push_back
#define pf push_front
#define sz size()
#define cnt continue
#define m_p make_pair
#define fr(i, l, r) for(int i = l; i <= r; ++ i)
#define rf(i, r, l) for(int i = r; i >= l; -- i)
#pragma GCC optimize(-O3)
#pragma GCC optimize(Ofast)
#pragma GCC optimize("unroll-loops")

using namespace __gnu_pbds;
using namespace std;

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;
typedef vector <ll> vl;
typedef vector <pll> vpl;

mt19937_64 rnd(time(NULL));

const ll N = 10;
const ll mtrxN = 10;
const ll oo = 2000000000;
//const ll oo = 228;
const ll B = 500;
const ll mod = 1e9 + 7;

struct mtrx{
    ll m[mtrxN][mtrxN] = {};
};
mtrx mtrx_mult(mtrx a, mtrx b){
    mtrx c;
    fr(i, 0, mtrxN - 1){
        fr(j, 0, mtrxN - 1){
            ll sum = 0;
            fr(x, 0, mtrxN - 1){
                sum += a.m[i][x] * b.m[x][j];
                sum %= mod;
            }
            c.m[i][j] = sum;
        }
    }
    return c;
}
mtrx mtrx_pow(mtrx a, ll n){
    mtrx res;
    fr(i, 0, mtrxN - 1)fr(j, 0, mtrxN - 1)res.m[i][j] = a.m[i][j];
    n --;
    while(n){
        if(n&1)res = mtrx_mult(res, a);
        a = mtrx_mult(a, a);
        n >>= 1;
    }
    return res;
}
ll _pow(ll a, ll n){
    ll r = 1;
    while(n){
        if(n&1)r = r * a % mod;
        a = a * a % mod;
        n >>= 1;
    }
    return r;
}
ll div(ll x, ll y, ll md){
    return x * _pow(y, md - 2) % md;
}

ll _gcd(ll x, ll y){
    if(x == 0)return y;
    if(y == 0)return x;
    return __gcd(x, y);
}

struct SegmentTreeSet{
    struct node{
        _set <pll> s;
        _set <pll> d;
        ll l = -1;
        ll r = -1;
    } emp;
    vector <node> t;

    void add_root(){
        t.pb(emp);
    }

    void ins(ll p, ll v, ll id, ll nw = 0, ll l = 0, ll r = oo){
        //cout << "p = " << p << " v = " << v << " id = " << id << " nw = " << nw << " l = " << l << " r = " << r << " t.sz = " << t.sz<< endl;
        t[nw].s.insert({v, id});
        t[nw].d.insert({v - p + 1, id});
        if(l != r){
            ll c = (l + r) / 2;
            if(p <= c){
                if(t[nw].l == -1){
                    t[nw].l = t.sz;
                    t.pb(emp);
                }
                ins(p, v, id, t[nw].l, l, c);
            }   else {
                if(t[nw].r == -1){
                    t[nw].r = t.sz;
                    t.pb(emp);
                }
                ins(p, v, id, t[nw].r, c + 1, r);
            }
        }
    }
    void ers(ll p, ll v, ll id, ll nw = 0, ll l = 0, ll r = oo){
        //cout << "p = " << p << " v = " << v << " id = " << id << " nw = " << nw << " l = " << l << " r = " << r << " t.sz = " << t.sz<< endl;
        t[nw].s.erase({v, id});
        t[nw].d.erase({v - p + 1, id});
        if(l != r){
            ll c = (l + r) / 2;
            if(p <= c){
                if(t[nw].l == -1){
                    t[nw].l = t.sz;
                    t.pb(emp);
                }
                ers(p, v, id, t[nw].l, l, c);
            }   else {
                if(t[nw].r == -1){
                    t[nw].r = t.sz;
                    t.pb(emp);
                }
                ers(p, v, id, t[nw].r, c + 1, r);
            }
        }
    }

    ll get1(ll l, ll r, ll k, ll nw = 0, ll tl = 0, ll tr = oo){
        if(l > r)return 0;
        if(tl == l && tr == r){
            pll p = {k, 0};
            return t[nw].s.sz - t[nw].s.order_of_key(p);
        }
        ll c = (tl + tr) / 2;
        if(t[nw].l == -1){
            t[nw].l = t.sz;
            t.pb(emp);
        }
        if(t[nw].r == -1){
            t[nw].r = t.sz;
            t.pb(emp);
        }
        return get1(l, min(r, c), k, t[nw].l, tl, c) + get1(max(l, c + 1), r, k, t[nw].r, c + 1, tr);
    }

    ll get2(ll l, ll r, ll k, ll nw = 0, ll tl = 0, ll tr = oo){
        if(l > r)return 0;
        if(tl == l && tr == r){
            pll p = {k, 0};
            return t[nw].d.sz - t[nw].d.order_of_key(p);
        }
        ll c = (tl + tr) / 2;
        if(t[nw].l == -1){
            t[nw].l = t.sz;
            t.pb(emp);
        }
        if(t[nw].r == -1){
            t[nw].r = t.sz;
            t.pb(emp);
        }

        return get2(l, min(r, c), k, t[nw].l, tl, c) + get2(max(l, c + 1), r, k, t[nw].r, c + 1, tr);
    }
};

pll ls[2000001];

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);
    ll T, t, lastans = 0, now = 1, wn = 0;
    cin >> T >> t;
    SegmentTreeSet tree;
    tree.add_root();

    while(T --){
        ll tp, a, b, l, r, id, k;
        cin >> tp;
        if(tp == 1){
            wn ++;
            cin >> a >> b;
            l = a ^ (lastans * t);
            r = b ^ (lastans * t);
            //???
            if(l > r)swap(l, r);
            //cout << "ins l..r " << l << ' ' << r << endl;
            ls[now] = {l, r};
            tree.ins(l, r, now);
            now ++;
        }
        if(tp == 2){
            wn --;
            cin >> id;
            //cout << "del l..r" << ls[id].ft << ' ' << ls[id].sd << endl;
            tree.ers(ls[id].ft, ls[id].sd, id);
        }
        if(tp == 3){
            cin >> a >> b >> k;
            if(k == 0){
                cout << wn << "\n";
                cnt;
            }

            l = a ^ (lastans * t);
            r = b ^ (lastans * t);
            //???
            if(l > r)swap(l, r);
            //cout << "ask: "<< l << ' ' << r << ' ' << k << endl;
            //cout << "get1 = " << tree.get1(1, l, l + k) << " get2 = " << tree.get2(l + 1, r, k) << endl;
            lastans = tree.get1(0, l, min(l + k - 1, oo)) + tree.get2(l + 1, r, k);
            //cout << "             ";
            cout << lastans << "\n";
        }
    }

    return 0;
}
/*
5 0
1 1 1
1 1 1
1 3 3
1 3 3
3 2 2 0

*/

Compilation message (stderr)

segments.cpp:17:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
 #pragma GCC optimize(-O3)
                      ^
segments.cpp:18:22: warning: '#pragma GCC optimize' is not a string or number [-Wpragmas]
 #pragma GCC optimize(Ofast)
                      ^~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25