oj.uz

Submission #519467

# Submission time Handle Problem Language Result Execution time Memory
519467 2022-01-26T12:05:56 Z Dasha_Gnedko Segments (IZhO18_segments) C++17
23 / 100
 5000 ms 19688 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 = 2e5 + 100;
const int M = 31;
const int mod = 998244353;
const int inf = 2e9 + 100;

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], 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});
    all.pb({{l, r}, id});
    if (sz(b) != sq) return;
    for(int j = 0; j < sq; j++)
        all.pop_back();
    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;
    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++)
    {
        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];
        }
    }
    uk++;
    b.clear();
    B = 0;
}

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 8 ms 9952 KB Output is correct
4 Correct 9 ms 9860 KB Output is correct
5 Correct 19 ms 10116 KB Output is correct
6 Correct 16 ms 10060 KB Output is correct
7 Correct 13 ms 9932 KB Output is correct
8 Correct 18 ms 10108 KB Output is correct
9 Correct 16 ms 10060 KB Output is correct
10 Correct 11 ms 10060 KB Output is correct
11 Correct 23 ms 10060 KB Output is correct
12 Correct 19 ms 10060 KB Output is correct
13 Correct 10 ms 10064 KB Output is correct
14 Correct 17 ms 10020 KB Output is correct
15 Correct 7 ms 9860 KB Output is correct
16 Correct 9 ms 9988 KB Output is correct
17 Correct 16 ms 9932 KB Output is correct
18 Correct 14 ms 10060 KB Output is correct
19 Correct 16 ms 9980 KB Output is correct
20 Correct 16 ms 9968 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5037 ms 15496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 218 ms 14448 KB Output is correct
2 Correct 212 ms 14540 KB Output is correct
3 Correct 226 ms 14724 KB Output is correct
4 Correct 230 ms 14456 KB Output is correct
5 Correct 691 ms 17640 KB Output is correct
6 Correct 649 ms 15780 KB Output is correct
7 Correct 683 ms 16276 KB Output is correct
8 Correct 679 ms 19488 KB Output is correct
9 Correct 676 ms 19396 KB Output is correct
10 Correct 584 ms 18264 KB Output is correct
11 Correct 341 ms 14632 KB Output is correct
12 Correct 589 ms 18332 KB Output is correct
13 Correct 569 ms 17992 KB Output is correct
14 Correct 491 ms 15816 KB Output is correct
15 Correct 471 ms 15696 KB Output is correct
16 Correct 414 ms 15344 KB Output is correct
17 Correct 593 ms 15224 KB Output is correct
18 Correct 662 ms 15084 KB Output is correct
19 Correct 671 ms 15136 KB Output is correct
20 Correct 591 ms 15112 KB Output is correct
21 Correct 350 ms 14884 KB Output is correct
22 Correct 513 ms 16260 KB Output is correct
23 Correct 554 ms 16724 KB Output is correct
24 Correct 554 ms 16284 KB Output is correct
25 Correct 228 ms 14536 KB Output is correct
26 Correct 215 ms 14528 KB Output is correct
27 Correct 216 ms 14488 KB Output is correct
28 Correct 227 ms 14524 KB Output is correct
29 Correct 558 ms 17620 KB Output is correct
30 Correct 604 ms 17708 KB Output is correct
31 Correct 669 ms 19432 KB Output is correct
32 Correct 598 ms 18260 KB Output is correct
33 Correct 569 ms 18048 KB Output is correct
34 Correct 470 ms 15580 KB Output is correct
35 Correct 565 ms 16724 KB Output is correct
36 Correct 582 ms 18336 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 598 ms 14752 KB Output is correct
2 Correct 541 ms 14692 KB Output is correct
3 Correct 592 ms 14704 KB Output is correct
4 Correct 623 ms 14732 KB Output is correct
5 Correct 4211 ms 17892 KB Output is correct
6 Correct 2451 ms 14276 KB Output is correct
7 Correct 3367 ms 18612 KB Output is correct
8 Correct 3411 ms 14448 KB Output is correct
9 Correct 4160 ms 16420 KB Output is correct
10 Correct 2354 ms 18572 KB Output is correct
11 Correct 3535 ms 15384 KB Output is correct
12 Correct 1012 ms 19688 KB Output is correct
13 Correct 3052 ms 18112 KB Output is correct
14 Correct 4160 ms 16236 KB Output is correct
15 Correct 1304 ms 19244 KB Output is correct
16 Correct 2760 ms 18204 KB Output is correct
17 Execution timed out 5100 ms 15360 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 8 ms 9952 KB Output is correct
4 Correct 9 ms 9860 KB Output is correct
5 Correct 19 ms 10116 KB Output is correct
6 Correct 16 ms 10060 KB Output is correct
7 Correct 13 ms 9932 KB Output is correct
8 Correct 18 ms 10108 KB Output is correct
9 Correct 16 ms 10060 KB Output is correct
10 Correct 11 ms 10060 KB Output is correct
11 Correct 23 ms 10060 KB Output is correct
12 Correct 19 ms 10060 KB Output is correct
13 Correct 10 ms 10064 KB Output is correct
14 Correct 17 ms 10020 KB Output is correct
15 Correct 7 ms 9860 KB Output is correct
16 Correct 9 ms 9988 KB Output is correct
17 Correct 16 ms 9932 KB Output is correct
18 Correct 14 ms 10060 KB Output is correct
19 Correct 16 ms 9980 KB Output is correct
20 Correct 16 ms 9968 KB Output is correct
21 Execution timed out 5037 ms 15496 KB Time limit exceeded
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 9676 KB Output is correct
2 Correct 5 ms 9720 KB Output is correct
3 Correct 8 ms 9952 KB Output is correct
4 Correct 9 ms 9860 KB Output is correct
5 Correct 19 ms 10116 KB Output is correct
6 Correct 16 ms 10060 KB Output is correct
7 Correct 13 ms 9932 KB Output is correct
8 Correct 18 ms 10108 KB Output is correct
9 Correct 16 ms 10060 KB Output is correct
10 Correct 11 ms 10060 KB Output is correct
11 Correct 23 ms 10060 KB Output is correct
12 Correct 19 ms 10060 KB Output is correct
13 Correct 10 ms 10064 KB Output is correct
14 Correct 17 ms 10020 KB Output is correct
15 Correct 7 ms 9860 KB Output is correct
16 Correct 9 ms 9988 KB Output is correct
17 Correct 16 ms 9932 KB Output is correct
18 Correct 14 ms 10060 KB Output is correct
19 Correct 16 ms 9980 KB Output is correct
20 Correct 16 ms 9968 KB Output is correct
21 Execution timed out 5037 ms 15496 KB Time limit exceeded
22 Halted 0 ms 0 KB -