Submission #516531

#	Time	Username	Problem	Language	Result	Execution time	Memory
516531		Dasha_Gnedko	Segments (IZhO18_segments)	C++17	23 / 100	449 ms	65540 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 = 1e5 + 100;
const int M = 31;
const int mod = 998244353;
const int inf = 1e9 + 7;

vector < int > ve;

struct Fenwick
{
    ordered_set < pair < int, int > > f[N];
    int n, state = 0;

    void build()
    {
        n = sz(ve);
//        f.resize(n);
    }

    void upd(int k, pair < int, int > p, int fl)
    {
        int l = 0, r = sz(ve) - 1, i = n;
        while (l <= r)
        {
            int mid = (l + r) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        for(; i < n; i = (i | (i + 1)))
        {
            if (fl) f[i].insert(p);
            else f[i].erase(p);
        }
    }

    int sum(int i, pair < int, int > p)
    {
        int ans = 0;
        for(; i >= 0; i = (i & (i + 1)) - 1)
            ans += f[i].order_of_key(p);
        return ans;
    }

    int get_ans(int i, int l, int r)
    {
        int ans = sum(i, {r + 1, -1});
        if (l) ans -= sum(i, {l, -1});
        return ans;
    }

    int get(int l, int r, int k)
    {
        if (l > r) return 0;
        int ans = get_ans(n - 1, l, r);
        int le = 0, ri = sz(ve) - 1, i = -1;
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                le = mid + 1;
            }
            else ri = mid - 1;
        }
        if (i) ans -= get_ans(i - 1, l, r);
        return ans;
    }

    int get1(int l, int r, int k)
    {
        if (l > r) return 0;
        int le = 0, ri = sz(ve) - 1, i = -1;
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                le = mid + 1;
            }
            else ri = mid - 1;
        }
        return get_ans(i, l, r);
    }

    int get2(int r, int k)
    {
        if (r < 0) return 0;
        int le = 0, ri = sz(ve) - 1, i = -1;
        while (le <= ri)
        {
            int mid = (le + ri) / 2;
            if (ve[mid] <= k)
            {
                i = mid;
                le = mid + 1;
            }
            else ri = mid - 1;
        }
        return sum(i, {r + 1, -1});
    }
};

Fenwick f1, f2;
vector < pair < pair < int, int >, pair < int, int > > > ask;
//ordered_set < pair < int, int > > st1, st2;

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;
    for(int i = 0; i < q; i++)
    {
        int type;
        cin >> type;
        if (type == 1)
        {
            int l, r;
            cin >> l >> r;
            ask.pb({{type, l}, {r, -1}});
        }
        if (type == 2)
        {
            int id;
            cin >> id;
            id--;
            ask.pb({{type, id}, {-1, -1}});
        }
        if (type == 3)
        {
            int l, r, k;
            cin >> l >> r >> k;
            ask.pb({{type, l}, {r, k}});
            ve.pb(k);
        }
    }
    ve.pb(1);
    sort(ve.begin(), ve.end());
    ve.erase(unique(ve.begin(), ve.end()), ve.end());
    f1.build();
    f2.build();
    f2.state = 1;
    vector < pair < int, int > > a;
    int ans = 0;
    for(auto to: ask)
    {
        int type = to.F.F;
        if (type == 1)
        {
            int l = to.F.S, r = to.S.F;
            l = (l ^ (T * ans));
            r = (r ^ (T * ans));
            if (l > r) swap(l, r);
            f1.upd(r - l + 1, {l, sz(a)}, 1);
            f2.upd(r - l + 1, {r, sz(a)}, 1);
//            st1.insert({l, sz(a)});
//            st2.insert({r, sz(a)});
            a.pb({l, r});
        }
        if (type == 2)
        {
            int id = to.F.S;
            int l = a[id].F, r = a[id].S;
            f1.upd(r - l + 1, {l, id}, 0);
            f2.upd(r - l + 1, {r, id}, 0);
//            st1.erase({l, id});
//            st2.erase({r, id});
        }
        if (type == 3)
        {
            int l = to.F.S, r = to.S.F, k = to.S.S;
            l = (l ^ (T * ans));
            r = (r ^ (T * ans));
            if (l > r) swap(l, r);
            ans = 0;
            if (r - l + 1 < k)
            {
                cout << 0 << endl;
                continue;
            }
            ans += f1.get(l + 1, r - k + 1, k);
            ans += f1.get1(0, l, 2e9 + 1);
            ans -= f2.get1(0, l + k - 2, 2e9 + 1);
            if (l + k - 2 >= l) ans += f2.get2(l + k - 2, k - 1);
            ans -= f1.get1(0, l, k - 1);
            cout << ans << endl;
        }
    }
}

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