Submission #519439

# Submission time Handle Problem Language Result Execution time Memory
519439 2022-01-26T11:15:44 Z Dasha_Gnedko Segments (IZhO18_segments) C++17
0 / 100
299 ms 29668 KB
#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;

const int sq = 1000;

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

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;
    b.pb({{l, r}, id});
    all.pb({{l, r}, id});
    if (sz(b) != sq) return;
    sort(all.begin(), all.end(), comp);
    for(int j = 0; j < uk; j++)
    {
        c[j].clear();
        d[j].clear();
        mn[j] = inf; mx[j] = -inf;
    }
    for(int i = 0; i < sz(all); i++)
    {
        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;
        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];
            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];
            pref[j][z] += used[d[j][z].S];
        }
    }
    b.clear();
}

void del(int l, int r, int id)
{
    used[id] = 0;
    if (pos[id] == -1) 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];
        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];
        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 = sz(all) - sz(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 -= sq;
            continue;
        }
        if (mn[j] < k)
        {
            for(int i = j * sq; i < (j + 1) * sq; i++)
            {
                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;
        }
    }
}
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 6 ms 5164 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 299 ms 29668 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 166 ms 17692 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 169 ms 17848 KB Output isn't correct
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 6 ms 5164 KB Output isn't correct
4 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Incorrect 6 ms 5164 KB Output isn't correct
4 Halted 0 ms 0 KB -