oj.uz

Submission #1083512

# Submission time Handle Problem Language Result Execution time Memory
1083512 2024-09-03T11:02:00 Z LOLOLO Segments (IZhO18_segments) C++17
0 / 100
 176 ms 1700 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

#define           s     second
#define           f     first
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 10;
const int block = 1e3;
int l[N], r[N];

struct {
    vector <pair <int, int>> in;
    vector <int> ls, rs;
    void add(int l, int r) {
        in.pb({l, r});
        if (sz(in) >= block) {
            for (auto x : in) {
                ls.pb(x.f);
                rs.pb(x.s);
            }

            in.clear();
            sort(all(ls));
            sort(all(rs));
        } 
    }

    int cal(int l, int r, int k) {
        if (r - l + 1 < k)
            return 0;

        int ans = 0;
        int p = upper_bound(all(ls), r - k + 1) - ls.begin();
        ans += sz(ls) - p;

        p = lower_bound(all(rs), l + k - 1) - rs.begin();
        ans += p;

        for (auto x : in) {
            if (min(x.s, r) - max(x.f, l) + 1 < k) 
                ans++;
        }

        return sz(ls) + sz(rs) + sz(in) - ans;
    }
} good, bad;

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

    int n, ss;
    cin >> n >> ss;
    int id = 1;

    int ans = 0;
    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;

        if (t == 1) {
            cin >> l[id] >> r[id];
            l[id] ^= (ans * ss), r[id] ^= (ans * ss);
            if (l[id] > r[id])
                swap(l[id], r[id]);

            good.add(l[id], r[id]);
            id++;
        }

        if (t == 2) {
            int tt;
            cin >> tt;
            bad.add(l[tt], r[tt]);
        }

        if (t == 3) {
            int l, r, k;
            cin >> l >> r >> k;
            l ^= (ans * ss), r ^= (ans * ss);
            if (l > r)
                swap(l, r);

            ans = good.cal(l, r, k) - bad.cal(l, r, k);
            
            cout << ans << "\n";
        }
    }
}

/*
6 1
1 1 2
3 2 4  2
1 3 5
3 2 3 1
2 1
3 0 3 1
*/

/*
6 0
1 3 10
1 3 5
3 6 10 6
2 1
1 3 10
3 6 4 2
*/

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 3 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

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

Subtask #3
0 / 16.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 3 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 3 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -