Submission #171510

#	Time	Username	Problem	Language	Result	Execution time	Memory
171510		theboatman	Segments (IZhO18_segments)	C++17	75 / 100	5085 ms	11904 KiB

segments

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int block_size = int(1337);
const int inf = int(1e9) + 10;

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

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

bool cmp_len(Seg a, Seg b) {
    return (a.r - a.l) < (b.r - b.l);
}

bool cmp_first(Seg a, Seg b) {
    return a.r > b.r;
}

bool cmp_second(Seg a, Seg b) {
    return a.l < b.l;
}


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

    int q, t;
    cin >> q >> t;

    int last_ans = 0, id = 1;
    vector <Seg> seg;
    for(int iq = 0; iq < q; iq++) {
        vector <Query> que;

        for(int i = 0; i < block_size && iq < q; i++, iq++) {
            int type;
            cin >> type;

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

                que.push_back({type, a, b, -1, id});
                id++;
            }

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

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

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

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

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

        vector <Seg> cur_seg, active;
        for(auto i : seg) {
            if (!del[i.id]) {
                cur_seg.push_back(i);
            }
            else {
                active.push_back(i);
            }
        }

        sort(cur_seg.begin(), cur_seg.end(), cmp_len);

        vector <int> mn_l, mx_l, mn_sz, mx_sz;
        vector <vector <Seg> > first, second;
        int n = sqrt(seg.size()) + 1;

        for(int i = 0; i < cur_seg.size(); i++) {
            vector <Seg> cur;
            for(int it = 0; it < n && i < cur_seg.size(); it++, i++) {
                cur.push_back(cur_seg[i]);
            }
            i--;

            int mn = inf, mx = -inf;
            int mn1 = inf, mx1 = -inf;
            for(auto it : cur) {
                mn = min(mn, it.l);
                mx = max(mx, it.l);

                mn1 = min(mn1, it.r - it.l + 1);
                mx1 = max(mx1, it.r - it.l + 1);
            }

            sort(cur.begin(), cur.end(), cmp_first);
            first.push_back(cur);

            sort(cur.begin(), cur.end(), cmp_second);
            second.push_back(cur);

            mn_l.push_back(mn);
            mx_l.push_back(mx);

            mx_sz.push_back(mx1);
            mn_sz.push_back(mn1);
        }

        del.assign(q + 1, 0);
        for(auto it : que) {
            if (it.type == 1) {
                int l = it.a ^ (last_ans * t), r = it.b ^ (last_ans * t);

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

                active.push_back({l, r, it.id});
            }

            if (it.type == 2) {
                del[it.id] = 1;
            }

            if (it.type == 3) {
                int l = it.a ^ (last_ans * t), r = it.b ^ (last_ans * t), k = it.k;

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

                int ans = 0;
                for(auto i : active) {
                    if (!del[i.id]) {
                        if (min(r, i.r) - max(l, i.l) + 1 >= k) {
                            ans++;
                        }
                    }
                }

                for(int x = 0; x < first.size(); x++) {
                    if (mx_sz[x] < k) {
                        continue;
                    }

                    if (mn_sz[x] < k && mx_sz[x] >= k) {
                        for(auto i : first[x]) {
                            if (i.r - i.l + 1 >= k && min(r, i.r) - max(l, i.l) + 1 >= k) {
                                ans++;
                            }
                        }
                        continue;
                    }

                    if (mx_l[x] <= l) {
                        int tl = 0, tr = first[x].size();
                        while(tl < tr) {
                            int c = tl + tr >> 1;

                            if (first[x][c].r - l + 1 >= k) {
                                tl = c + 1;
                            }
                            else {
                                tr = c;
                            }
                        }

                        ans += tl;
                        continue;
                    }

                    if (mn_l[x] > l) {
                        int tl = 0, tr = second[x].size();
                        while(tl < tr) {
                            int c = tl + tr >> 1;

                            if (r - second[x][c].l + 1 >= k) {
                                tl = c + 1;
                            }
                            else {
                                tr = c;
                            }
                        }

                        ans += tl;
                        continue;
                    }

                    for(auto i : first[x]) {
                        if (min(r, i.r) - max(l, i.l) + 1 >= k) {
                            ans++;
                        }
                    }

                }

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

        for(auto i : active) {
            if (!del[i.id]) {
                cur_seg.push_back(i);
            }
        }

        seg = cur_seg;
    }

    return 0;
}
/*
*/

Compilation message (stderr)

segments.cpp: In function 'int main()':
segments.cpp:93:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < cur_seg.size(); i++) {
                        ~~^~~~~~~~~~~~~~~~
segments.cpp:95:41: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int it = 0; it < n && i < cur_seg.size(); it++, i++) {
                                       ~~^~~~~~~~~~~~~~~~
segments.cpp:155:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(int x = 0; x < first.size(); x++) {
                                ~~^~~~~~~~~~~~~~
segments.cpp:172:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                             int c = tl + tr >> 1;
                                     ~~~^~~~
segments.cpp:189:40: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
                             int c = tl + tr >> 1;
                                     ~~~^~~~

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