Submission #683578

#	Time	Username	Problem	Language	Result	Execution time	Memory
683578		opPO	Segments (IZhO18_segments)	C++17	23 / 100	162 ms	19856 KiB

segments

#pragma GCC optimize("O3,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define int long long
#define f first
#define s second
#define pb push_back
#define ld long double
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define vec vector

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using oset = tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
const ld eps = 1e-6;
const int mod = 998244353;
const int oo = 2e9;
const ll OO = 2e18;
const int N = 1e5 + 10;

struct Query
{
    int type;
    int a;
    int b;
    int k;
    int id;

    Query(int type, int a, int b) : type(type), a(a), b(b) {}

    Query(int type, int id) : type(type), id(id) {}

    Query(int type, int a, int b, int k) : type(type), a(a), b(b), k(k) {}
};

int intersection(pii a, pii b)
{
    return max(0LL, min(a.s, b.s) - max(a.f, b.f) + 1);
}

void solve()
{
    int q, t;
    cin >> q >> t;
    vec<Query> qs;
    bool g3 = true;
    for (int qr = 0; qr < q; qr++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int a, b;
            cin >> a >> b;
            qs.pb(Query(type, a, b));
        }
        else if (type == 2)
        {
            int id;
            cin >> id;
            qs.pb(Query(type, id));
        }
        else
        {
            int a, b, k;
            cin >> a >> b >> k;
            if (k != 1) g3 = false;
            qs.pb(Query(type, a, b, k));
        }
    }
    if (q <= 5e3)
    {
        vec<pii> segments;
        vec<pii> seg_by_id(q + 1);
        int ID = 0, last_ans = 0;
        for (int qr = 0; qr < q; qr++)
        {
            Query Q = qs[qr];
            if (Q.type == 1)
            {
                ID++;
                int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
                if (l > r) swap(l, r);
                segments.pb({l, r});
                seg_by_id[ID] = segments.back();
            }
            else if (Q.type == 2)
            {
                pii seg = seg_by_id[Q.id];
                segments.erase(find(all(segments), seg));
            }
            else
            {
                int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
                if (l > r) swap(l, r);
                int res = 0;
                for (auto &seg : segments) if (intersection(seg, {l, r}) >= Q.k) res++;
                cout << res << "\n";
                last_ans = res;
            }
        }
        return;
    }
    if (g3)
    {
        vec<pii> seg_by_id(q + 1);
        int ID = 0, last_ans = 0;
        oset lefts, rights;
        for (int qr = 0; qr < q; qr++)
        {
            Query Q = qs[qr];
            if (Q.type == 1)
            {
                ID++;
                int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
                if (l > r) swap(l, r);
                lefts.insert({l, ID});
                rights.insert({r, ID});
                seg_by_id[ID] = {l, r};
            }
            else if (Q.type == 2)
            {
                pii seg = seg_by_id[Q.id];
                lefts.erase(lefts.lower_bound({seg.f, -OO}));
                rights.erase(rights.lower_bound({seg.s, -OO}));
            }
            else
            {
                int l = (Q.a ^ (t * last_ans)), r = (Q.b ^ (t * last_ans));
                if (l > r) swap(l, r);
                int res = sz(lefts);
                res -= rights.order_of_key({l, -OO});
                res -= sz(lefts) - lefts.order_of_key({r + 1, -OO});
                cout << res << "\n";
                last_ans = res;
            }
        }
        return;
    }
}

int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

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