Submission #100264

#	Time	Username	Problem	Language	Result	Execution time	Memory
100264		choikiwon	Segments (IZhO18_segments)	C++17	100 / 100	4698 ms	10980 KiB

segments

#include<bits/stdc++.h>
using namespace std;

typedef pair<int, int> pii;

const int MN = 200010;
const int SQ = 2000;

int Q, T, N, n;
pii seg[MN], tmp1[MN], tmp2[MN];
int chk[MN], mn[MN], mx[MN];
vector<int> add, del;

bool cmp(pii a, pii b) {
    return a.second < b.second;
}

void relax() {
    if(add.size() > SQ || del.size() > SQ) {
        for(int i = 0; i < add.size(); i++) chk[ add[i] ] = 1;
        for(int i = 0; i < del.size(); i++) chk[ del[i] ] = 0;
        add.clear();
        del.clear();

        n = 0;
        for(int i = 0; i < N; i++) if(chk[i]) {
            tmp1[n] = pii(seg[i].second, seg[i].first);
            tmp2[n] = pii(seg[i].second - seg[i].first, seg[i].first);
            n++;
        }
        sort(tmp1, tmp1 + n, cmp);
        sort(tmp2, tmp2 + n, cmp);

        for(int i = 0; i < n; i += SQ) {
            int l = i;
            int r = min(n, i + SQ) - 1;
            mn[i] = tmp1[l].second;
            mx[i] = tmp1[r].second;
            sort(tmp1 + l, tmp1 + r + 1);
            sort(tmp2 + l, tmp2 + r + 1);
        }
    }
}

int main() {
    scanf("%d %d", &Q, &T);

    int ans = 0;
    while(Q--) {
        relax();

        int t; scanf("%d", &t);

        if(t == 1) {
            int a, b; scanf("%d %d", &a, &b);
            if(T) {
                a ^= ans;
                b ^= ans;
            }
            if(a > b) swap(a, b);

            //cout << "add : " << a << ' ' << b << endl;

            add.push_back(N);
            seg[N++] = pii(a, b);
        }
        if(t == 2) {
            int id; scanf("%d", &id);
            id--;
            del.push_back(id);
        }
        if(t == 3) {
            int a, b, k; scanf("%d %d %d", &a, &b, &k);
            k--;
            if(T) {
                a ^= ans;
                b ^= ans;
            }
            if(a > b) swap(a, b);

            //cout << "query : " << a << ' ' << b << ' ' << k << endl;

            if(b - a < k) {
                ans = 0;
                printf("%d\n", ans);
                continue;
            }

            ans = 0;
            for(int i = 0; i < add.size(); i++) if(min(b, seg[ add[i] ].second) - max(a, seg[ add[i] ].first) >= k) ans++;
            for(int i = 0; i < del.size(); i++) if(min(b, seg[ del[i] ].second) - max(a, seg[ del[i] ].first) >= k) ans--;

            if(k == -1) {
                ans += n;
                printf("%d\n", ans);
                continue;
            }

            for(int i = 0; i < n; i += SQ) {
                int l = i;
                int r = min(n, i + SQ) - 1;

                if(mx[i] < a) {
                    int x = lower_bound(tmp1 + l, tmp1 + r + 1, pii(a + k, -1)) - tmp1;
                    ans += r + 1 - x;
                }
                else {
                    for(int j = l; j <= r; j++) {
                        if(tmp1[j].second < a && tmp1[j].first >= a + k) ans++;
                    }
                    break;
                }
            }
            for(int i = 0; i < n; i += SQ) {
                int l = i;
                int r = min(n, i + SQ) - 1;

                if(b - k < mn[i] || mx[i] < a) continue;
                if(a <= mn[i] && mx[i] <= b - k) {
                    int x = lower_bound(tmp2 + l, tmp2 + r + 1, pii(k, -1)) - tmp2;
                    ans += r + 1 - x;
                }
                else {
                    for(int j = l; j <= r; j++) {
                        if(a <= tmp2[j].second && tmp2[j].second <= b - k && tmp2[j].first >= k) ans++;
                    }
                }
            }
            printf("%d\n", ans);
        }
    }
}

Compilation message (stderr)

segments.cpp: In function 'void relax()':
segments.cpp:20:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < add.size(); i++) chk[ add[i] ] = 1;
                        ~~^~~~~~~~~~~~
segments.cpp:21:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(int i = 0; i < del.size(); i++) chk[ del[i] ] = 0;
                        ~~^~~~~~~~~~~~
segments.cpp: In function 'int main()':
segments.cpp:90:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < add.size(); i++) if(min(b, seg[ add[i] ].second) - max(a, seg[ add[i] ].first) >= k) ans++;
                            ~~^~~~~~~~~~~~
segments.cpp:91:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int i = 0; i < del.size(); i++) if(min(b, seg[ del[i] ].second) - max(a, seg[ del[i] ].first) >= k) ans--;
                            ~~^~~~~~~~~~~~
segments.cpp:46:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &Q, &T);
     ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:52:21: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         int t; scanf("%d", &t);
                ~~~~~^~~~~~~~~~
segments.cpp:55:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int a, b; scanf("%d %d", &a, &b);
                       ~~~~~^~~~~~~~~~~~~~~~~
segments.cpp:68:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int id; scanf("%d", &id);
                     ~~~~~^~~~~~~~~~~
segments.cpp:73:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             int a, b, k; scanf("%d %d %d", &a, &b, &k);
                          ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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