oj.uz

Submission #100251

# Submission time Handle Problem Language Result Execution time Memory
100251 2019-03-10T06:10:57 Z choikiwon Segments (IZhO18_segments) C++17
7 / 100
 3720 ms 41984 KB 
#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--;

            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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 13 ms 5120 KB Output is correct
4 Correct 13 ms 5220 KB Output is correct
5 Correct 28 ms 7268 KB Output is correct
6 Correct 23 ms 6756 KB Output is correct
7 Correct 15 ms 5504 KB Output is correct
8 Correct 23 ms 6596 KB Output is correct
9 Correct 21 ms 6588 KB Output is correct
10 Correct 25 ms 7320 KB Output is correct
11 Correct 23 ms 6196 KB Output is correct
12 Correct 20 ms 6144 KB Output is correct
13 Correct 34 ms 7268 KB Output is correct
14 Correct 30 ms 6460 KB Output is correct
15 Correct 13 ms 5120 KB Output is correct
16 Correct 14 ms 5248 KB Output is correct
17 Correct 17 ms 5940 KB Output is correct
18 Correct 28 ms 7420 KB Output is correct
19 Correct 17 ms 5888 KB Output is correct
20 Correct 22 ms 6016 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2700 ms 37560 KB Output is correct
2 Correct 2692 ms 37652 KB Output is correct
3 Correct 2467 ms 37544 KB Output is correct
4 Runtime error 3292 ms 40980 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
5 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 7544 KB Output is correct
2 Runtime error 162 ms 41984 KB Execution killed with signal 9 (could be triggered by violating memory limits)
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 7732 KB Output is correct
2 Correct 154 ms 7784 KB Output is correct
3 Correct 148 ms 7672 KB Output is correct
4 Correct 149 ms 7928 KB Output is correct
5 Runtime error 3720 ms 41984 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 13 ms 5120 KB Output is correct
4 Correct 13 ms 5220 KB Output is correct
5 Correct 28 ms 7268 KB Output is correct
6 Correct 23 ms 6756 KB Output is correct
7 Correct 15 ms 5504 KB Output is correct
8 Correct 23 ms 6596 KB Output is correct
9 Correct 21 ms 6588 KB Output is correct
10 Correct 25 ms 7320 KB Output is correct
11 Correct 23 ms 6196 KB Output is correct
12 Correct 20 ms 6144 KB Output is correct
13 Correct 34 ms 7268 KB Output is correct
14 Correct 30 ms 6460 KB Output is correct
15 Correct 13 ms 5120 KB Output is correct
16 Correct 14 ms 5248 KB Output is correct
17 Correct 17 ms 5940 KB Output is correct
18 Correct 28 ms 7420 KB Output is correct
19 Correct 17 ms 5888 KB Output is correct
20 Correct 22 ms 6016 KB Output is correct
21 Correct 2700 ms 37560 KB Output is correct
22 Correct 2692 ms 37652 KB Output is correct
23 Correct 2467 ms 37544 KB Output is correct
24 Runtime error 3292 ms 40980 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
25 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5120 KB Output is correct
2 Correct 6 ms 5120 KB Output is correct
3 Correct 13 ms 5120 KB Output is correct
4 Correct 13 ms 5220 KB Output is correct
5 Correct 28 ms 7268 KB Output is correct
6 Correct 23 ms 6756 KB Output is correct
7 Correct 15 ms 5504 KB Output is correct
8 Correct 23 ms 6596 KB Output is correct
9 Correct 21 ms 6588 KB Output is correct
10 Correct 25 ms 7320 KB Output is correct
11 Correct 23 ms 6196 KB Output is correct
12 Correct 20 ms 6144 KB Output is correct
13 Correct 34 ms 7268 KB Output is correct
14 Correct 30 ms 6460 KB Output is correct
15 Correct 13 ms 5120 KB Output is correct
16 Correct 14 ms 5248 KB Output is correct
17 Correct 17 ms 5940 KB Output is correct
18 Correct 28 ms 7420 KB Output is correct
19 Correct 17 ms 5888 KB Output is correct
20 Correct 22 ms 6016 KB Output is correct
21 Correct 2700 ms 37560 KB Output is correct
22 Correct 2692 ms 37652 KB Output is correct
23 Correct 2467 ms 37544 KB Output is correct
24 Runtime error 3292 ms 40980 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
25 Halted 0 ms 0 KB -