Submission #519497

#	Time	Username	Problem	Language	Result	Execution time	Memory
519497		Dasha_Gnedko	Segments (IZhO18_segments)	C++17	100 / 100	1851 ms	32336 KiB

segments

#include <bits/stdc++.h>

//#include <ext/pb_ds/detail/standard_policies.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>

//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx2")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")

using namespace std;

//using namespace __gnu_pbds;
//template <typename T> using ordered_set = tree <T, null_type, less < T >, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(time(0));

#define ll long long
#define ld long double
#define pb push_back
#define F first
#define S second
#define TIME clock() * 1.0 / CLOCKS_PER_SEC
#define sz(a) int32_t(a.size())
#define endl '\n'
//#define int long long

const int N = 2e5 + 100;
const int M = 31;
const int mod = 998244353;
const int inf = 2e9 + 100;

const int sq = 1500;

vector < pair < int, int > > c[N], d[N];
vector < pair < pair < int, int >, int > > b, all;
int pref[N / sq + 5][sq + 1], suf[N / sq + 5][sq + 1];
int mn[N], mx[N], uk, used[N], pos[N], All, B;

bool comp(pair < pair < int, int >, int > a, pair < pair < int, int >, int > b)
{
    return (a.F.S - a.F.F < b.F.S - b.F.F);
}

void add(int l, int r, int id)
{
    used[id] = 1;
    pos[id] = -1;
    All++; B++;
    b.pb({{l, r}, id});
    if (sz(b) != sq) return;
    All = B = 0;
    sort(b.begin(), b.end(), comp);
    vector < pair < pair < int, int >, int > > ve;
    int i = 0, j = 0;
    while (i < sz(all) || j < sz(b))
    {
        if ((i < sz(all) && j < sz(b) && all[i].F.S - all[i].F.F <= b[j].F.S - b[j].F.F) || j == sz(b)) ve.pb(all[i++]);
        else ve.pb(b[j++]);
    }
    all = ve;
    uk++;
    for(int j = 0; j < uk; j++)
    {
        c[j].clear();
        d[j].clear();
        mn[j] = -1; mx[j] = 0;
    }
    for(int i = 0; i < sz(all); i++)
    {
        All += used[all[i].S];
        int j = i / sq;
        c[j].pb({all[i].F.F, all[i].S});
        d[j].pb({all[i].F.S, all[i].S});
        pos[all[i].S] = j;
        if (mn[j] == -1) mn[j] = all[i].F.S - all[i].F.F + 1;
        else mn[j] = min(mn[j], all[i].F.S - all[i].F.F + 1);
        mx[j] = max(mx[j], all[i].F.S - all[i].F.F + 1);
    }
    for(int j = 0; j < uk; j++)
    {
        sort(c[j].begin(), c[j].end());
        sort(d[j].begin(), d[j].end());
        for(int z = sz(c[j]) - 1; z >= 0; z--)
        {
            if (z + 1 < sz(c[j])) suf[j][z] = suf[j][z + 1];
            else suf[j][z] = 0;
            suf[j][z] += used[c[j][z].S];
        }
        for(int z = 0; z < sz(c[j]); z++)
        {
            if (z) pref[j][z] = pref[j][z - 1];
            else pref[j][z] = 0;
            pref[j][z] += used[d[j][z].S];
        }
    }
    b.clear();
}

void del(int l, int r, int id)
{
    used[id] = 0;
    All--;
    if (pos[id] == -1)
    {
        B--;
        return;
    }
    int j = pos[id];
    for(int z = sz(c[j]) - 1; z >= 0; z--)
    {
        if (z + 1 < sz(c[j])) suf[j][z] = suf[j][z + 1];
        else suf[j][z] = 0;
        suf[j][z] += used[c[j][z].S];
    }
    for(int z = 0; z < sz(c[j]); z++)
    {
        if (z) pref[j][z] = pref[j][z - 1];
        else pref[j][z] = 0;
        pref[j][z] += used[d[j][z].S];
    }
}

int get(int l, int r, int k)
{
    if (r - l + 1 < k) return 0;
    int ans = All - B;
    for(auto to: b)
        if (used[to.S]) ans += (min(to.F.S, r) - max(to.F.F, l) + 1 >= k);
    for(int j = 0; j < uk; j++)
    {
        if (mx[j] < k)
        {
            ans -= suf[j][0];
            continue;
        }
        if (mn[j] < k)
        {
            for(int i = j * sq; i < (j + 1) * sq; i++)
            {
                if (!used[all[i].S]) continue;
                auto to = all[i];
                ans -= (min(to.F.S, r) - max(to.F.F, l) + 1 < k);
            }
            continue;
        }
        int le = 0, ri = sz(c[j]) - 1, gr = sz(c[j]);
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (c[j][mid].F > r - k + 1)
            {
                gr = mid;
                ri = mid - 1;
            }
            else le = mid + 1;
        }
        if (gr < sz(c[j])) ans -= suf[j][gr];
        le = 0; ri = sz(d[j]) - 1; int gl = sz(d[j]);
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (d[j][mid].F < l + k - 1)
            {
                gl = mid;
                le = mid + 1;
            }
            else ri = mid - 1;
        }
        if (gl < sz(d[j])) ans -= pref[j][gl];
    }
    return ans;
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif // LOCAL

    int q, T;
    cin >> q >> T;
    vector < pair < int, int > > a;
    int ans = 0;
    while (q--)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r;
            cin >> l >> r;
            l = (l ^ (T * ans));
            r = (r ^ (T * ans));
            if (l > r) swap(l, r);
            add(l, r, sz(a));
            a.pb({l, r});
        }
        if (type == 2)
        {
            int id;
            cin >> id; id--;
            int l = a[id].F, r = a[id].S;
            del(l, r, id);
        }
        if (type == 3)
        {
            int l, r, k;
            cin >> l >> r >> k;
            l = (l ^ (T * ans));
            r = (r ^ (T * ans));
            if (l > r) swap(l, r);
            ans = get(l, r, k);
            cout << ans << endl;
        }
    }
}

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