Submission #100252

#	Time	Username	Problem	Language	Result	Execution time	Memory
100252		choikiwon	Segments (IZhO18_segments)	C++17	7 / 100	4106 ms	41984 KiB

segments

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

typedef pair<int, int> pii;

const int MN = 200010;
const int SQ = 1000;

int Q, T, N;
pii seg[MN];
int chk[MN];
vector<int> add, del;

int Xn;
vector<int> X, V[MN];
unordered_map<int, int> dx;

vector<int> mrg(vector<int> &a, vector<int> &b) {
    vector<int> ret;

    int pos1 = 0, pos2 = 0;
    while(pos1 < a.size() && pos2 < b.size()) {
        if(a[pos1] < b[pos2]) ret.push_back(a[pos1++]);
        else ret.push_back(b[pos2++]);
    }
    while(pos1 < a.size()) ret.push_back(a[pos1++]);
    while(pos2 < b.size()) ret.push_back(b[pos2++]);
    return ret;
}

struct BIT {
    vector<vector<int> > tree;
    void init() {
        tree = vector<vector<int> >(4 * Xn);
        build(0, Xn - 1, 1);
    }
    void build(int l, int r, int n) {
        if(l == r) {
            tree[n] = V[l];
            sort(tree[n].begin(), tree[n].end());
            return;
        }
        int m = (l + r)>>1;
        build(l, m, 2*n);
        build(m + 1, r, 2*n + 1);
        tree[n] = mrg(tree[2*n], tree[2*n + 1]);
    }
    int quer(int a, int b, int k, int l, int r, int n) {
        if(b < l || r < a) return 0;
        if(a <= l && r <= b) {
            int x = lower_bound(tree[n].begin(), tree[n].end(), k) - tree[n].begin();
            return (int)tree[n].size() - x;
        }
        int m = (l + r)>>1;
        int L = quer(a, b, k, l, m, 2*n);
        int R = quer(a, b, k, m + 1, r, 2*n + 1);
        return L + R;
    }
} bit1, bit2;

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();

        X.clear();
        dx.clear();
        for(int i = 0; i < N; i++) if(chk[i]) {
            X.push_back(seg[i].first);
        }
        sort(X.begin(), X.end());
        X.resize(unique(X.begin(), X.end()) - X.begin());
        Xn = X.size();
        for(int i = 0; i < Xn; i++) dx[X[i]] = i;

        for(int i = 0; i < Xn; i++) V[i].clear();
        for(int i = 0; i < N; i++) if(chk[i]) {
            V[ dx[seg[i].first] ].push_back(seg[i].second);
        }
        bit1.init();

        for(int i = 0; i < Xn; i++) V[i].clear();
        for(int i = 0; i < N; i++) if(chk[i]) {
            V[ dx[seg[i].first] ].push_back(seg[i].second - seg[i].first);
        }
        bit2.init();
    }
}

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(Xn) {
                int l = lower_bound(X.begin(), X.end(), a) - X.begin();
                int r = upper_bound(X.begin(), X.end(), b - k) - X.begin();

                ans += bit1.quer(0, l - 1, a + k, 0, Xn - 1, 1);
                ans += bit2.quer(l, r - 1, k, 0, Xn - 1, 1);
            }

            printf("%d\n", ans);
        }
    }
}

Compilation message (stderr)

segments.cpp: In function 'std::vector<int> mrg(std::vector<int>&, std::vector<int>&)':
segments.cpp:22:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size() && pos2 < b.size()) {
           ~~~~~^~~~~~~~~~
segments.cpp:22:35: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size() && pos2 < b.size()) {
                              ~~~~~^~~~~~~~~~
segments.cpp:26:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos1 < a.size()) ret.push_back(a[pos1++]);
           ~~~~~^~~~~~~~~~
segments.cpp:27:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos2 < b.size()) ret.push_back(b[pos2++]);
           ~~~~~^~~~~~~~~~
segments.cpp: In function 'void relax()':
segments.cpp:63: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:64: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:137: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:138: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:93: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:99: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:102: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:115: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:120: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: 0 / 15
• Subtask 3: 0 / 16
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20
• Subtask 6: 0 / 25