Submission #171071

#	Time	Username	Problem	Language	Result	Execution time	Memory
171071		theboatman	Segments (IZhO18_segments)	C++17	0 / 100	3030 ms	4464 KiB

segments

#include <bits/stdc++.h>

#define y1 theboatman
#define make_struct(args...) {args}

using namespace std;

const int block_size = 400;

struct query {
    int type, a, b, k, id;
};

struct seg {
    int l, r, id;
};

bool cmp_l(seg a, seg b) {
    return a.l < b.l;
}

bool cmp_r(seg a, seg b) {
    return a.r < b.r;
}

bool cmp_id(seg a, seg b) {
    return a.id < b.id;
}

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

    int n, t;
    cin >> n >> t;

    vector <seg> seq;
    int now = 1, last_ans = 0;

    for(int it = 0; it < n; it++) {
        if (it % block_size == 0) {
            vector <query> que;
            for(int i = it; i < it + block_size && i < n; i++) {
                int type;
                cin >> type;

                if (type == 1) {
                    int a, b;
                    cin >> a >> b;

                    que.push_back(make_struct(type, a, b, -1, now++));
                }

                if (type == 2) {
                    int id;
                    cin >> id;

                    que.push_back(make_struct(type, -1, -1, -1, id));
                }

                if (type == 3) {
                    int a, b, k;
                    cin >> a >> b >> k;

                    que.push_back(make_struct(type, a, b, k, -1));
                }
            }

            vector <int> del(n + 1);
            for(auto i : que) {
                if (i.type == 2) {
                    del[i.id] = 1;
                }
            }

            vector <seg> new_seq, used;
            for(auto i : seq) {
                if (!del[i.id]) {
                    new_seq.push_back(i);
                }
                else {
                    used.push_back(i);
                }
            }

            seq = new_seq;

            int block = sqrt(seq.size()) + 1;
            vector <int> mx, mn;
            vector <vector <seg> > dec, dec1;

            sort(seq.begin(), seq.end(), cmp_l);

            for(int it = 0; it < seq.size(); it++) {
                if (it % block == 0) {
                    vector <seg> a;
                    for(int i = it; i < it + block && i < seq.size(); i++) {
                        a.push_back(seq[i]);
                    }

                    vector <seg> a1 = a;
                    for(auto &i : a1) {
                        i.id = i.r - i.l + 1;
                    }

                    mx.push_back(a.back().l);
                    mn.push_back(a[0].l);

                    sort(a.begin(), a.end(), cmp_r);
                    sort(a1.begin(), a1.end(), cmp_id);

                    dec.push_back(a);
                    dec1.push_back(a1);
                }
            }

            vector <int> del1(n + 1);
            vector <seg> lazy;

            for(auto i : que) {
                if (i.type == 1) {
                    int l = (last_ans * t) ^ i.a;
                    int r = (last_ans * t) ^ i.b;

                    if (l > r) {
                        swap(l, r);
                    }

                    if (!del[i.id]) {
                        lazy.push_back(make_struct(l, r, i.id));
                    }

                    used.push_back(make_struct(l, r, i.id));
                }

                if (i.type == 2) {
                    del1[i.id] = 1;
                }

                if (i.type == 3) {
                    int ans = 0;

                    int l = (last_ans * t) ^ i.a;
                    int r = (last_ans * t) ^ i.b;

                    if (l > r) {
                        swap(l, r);
                    }

                    for(auto it : used) {
                        if (!del1[it.id]) {
                            int L = max(l, it.l);
                            int R = min(r, it.r);

                            if (!i.k || (L <= R && R - L + 1 >= i.k)) {
                                ans++;
                            }
                        }
                    }


                    // first case
                    for(int it = 0; it < mx.size(); it++) {
                        if (mx[it] < l && r - l + 1 >= i.k) {
                            int tl = 0, tr = dec[it].size();
                            while(tl < tr) {
                                int mid = tl + tr >> 1;
                                if (l + i.k - 1 <= dec[it][mid].r) {
                                    tl = mid + 1;
                                }
                                else {
                                    tr = mid;
                                }
                            }

                            ans += tl;
                        }

                        if (mx[it] >= l && mn[it] < l && r - l + 1 >= i.k) {
                            for(auto q : dec[it]) {
                                if (l + i.k - 1 <= q.r && q.l < l) {
                                    ans++;
                                }
                            }
                        }
                    }

                    // second case
                    for(int it = 0; it < mx.size(); it++) {
                        if (mn[it] >= l && mx[it] <= r - i.k + 1) {
                            int tl = 0, tr = dec[it].size();
                            while(tl < tr) {
                                int mid = tl + tr >> 1;
                                if (dec[it][mid].id < i.k) {
                                    tl = mid + 1;
                                }
                                else {
                                    tr = mid;
                                }
                            }

                            ans += dec[it].size() - tl;
                        }

                        if (mx[it] >= l && mn[it] <= r - i.k + 1) {
                            for(auto q : dec[it]) {
                                if (q.l >= l && q.id >= i.k) {
                                    ans++;
                                }
                            }
                        }
                    }



                    cout << ans << "\n";
                    last_ans = ans;
                }

            }

            for(auto i : lazy) {
                seq.push_back(i);
            }
        }

    }

    return 0;
}
/*
0 1 2 3

l, r
L, R - query

if l < L :
    L + k - 1 <= r && R - L + 1 >= k

if l >= L
    l + k - 1 <= r && R - k + 1 >= l
    r - l + 1 >= k && l <= R - k + 1


O(n * block_size + n / block_size * n + n / block_size * log(n) + n * sqrt(n) * log(sqrt(n))

1.8 + 0.4 + 0.0004 + (3.4) / 2 += 3
*/

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:94:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int it = 0; it < seq.size(); it++) {
                             ~~~^~~~~~~~~~~~
segments.cpp:97:57: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(int i = it; i < it + block && i < seq.size(); i++) {
                                                       ~~^~~~~~~~~~~~
segments.cpp:163:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(int it = 0; it < mx.size(); it++) {
                                     ~~~^~~~~~~~~~~
segments.cpp:167:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                                 int mid = tl + tr >> 1;
                                           ~~~^~~~
segments.cpp:189:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                     for(int it = 0; it < mx.size(); it++) {
                                     ~~~^~~~~~~~~~~
segments.cpp:193:46: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                                 int mid = tl + tr >> 1;
                                           ~~~^~~~

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