oj.uz

Submission #683577

# Submission time Handle Problem Language Result Execution time Memory
683577 2023-01-18T18:43:01 Z opPO Segments (IZhO18_segments) C++17
7 / 100
 48 ms 7740 KB 
#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 -= lefts.order_of_key({l, -OO});
                res -= sz(rights) - rights.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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 820 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 9 ms 820 KB Output is correct
7 Correct 4 ms 816 KB Output is correct
8 Correct 6 ms 816 KB Output is correct
9 Correct 6 ms 824 KB Output is correct
10 Correct 4 ms 912 KB Output is correct
11 Correct 13 ms 820 KB Output is correct
12 Correct 17 ms 812 KB Output is correct
13 Correct 4 ms 924 KB Output is correct
14 Correct 6 ms 820 KB Output is correct
15 Correct 2 ms 820 KB Output is correct
16 Correct 2 ms 820 KB Output is correct
17 Correct 5 ms 820 KB Output is correct
18 Correct 5 ms 812 KB Output is correct
19 Correct 6 ms 848 KB Output is correct
20 Correct 5 ms 820 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 33 ms 7268 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 48 ms 7740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 34 ms 7032 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 820 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 9 ms 820 KB Output is correct
7 Correct 4 ms 816 KB Output is correct
8 Correct 6 ms 816 KB Output is correct
9 Correct 6 ms 824 KB Output is correct
10 Correct 4 ms 912 KB Output is correct
11 Correct 13 ms 820 KB Output is correct
12 Correct 17 ms 812 KB Output is correct
13 Correct 4 ms 924 KB Output is correct
14 Correct 6 ms 820 KB Output is correct
15 Correct 2 ms 820 KB Output is correct
16 Correct 2 ms 820 KB Output is correct
17 Correct 5 ms 820 KB Output is correct
18 Correct 5 ms 812 KB Output is correct
19 Correct 6 ms 848 KB Output is correct
20 Correct 5 ms 820 KB Output is correct
21 Incorrect 33 ms 7268 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 3 ms 820 KB Output is correct
4 Correct 2 ms 816 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 9 ms 820 KB Output is correct
7 Correct 4 ms 816 KB Output is correct
8 Correct 6 ms 816 KB Output is correct
9 Correct 6 ms 824 KB Output is correct
10 Correct 4 ms 912 KB Output is correct
11 Correct 13 ms 820 KB Output is correct
12 Correct 17 ms 812 KB Output is correct
13 Correct 4 ms 924 KB Output is correct
14 Correct 6 ms 820 KB Output is correct
15 Correct 2 ms 820 KB Output is correct
16 Correct 2 ms 820 KB Output is correct
17 Correct 5 ms 820 KB Output is correct
18 Correct 5 ms 812 KB Output is correct
19 Correct 6 ms 848 KB Output is correct
20 Correct 5 ms 820 KB Output is correct
21 Incorrect 33 ms 7268 KB Output isn't correct
22 Halted 0 ms 0 KB -