oj.uz

Submission #42823

# Submission time Handle Problem Language Result Execution time Memory
42823 2018-03-04T15:23:55 Z minhtung0404 Segments (IZhO18_segments) C++14
7 / 100
 2911 ms 1088 KB 
//https://oj.uz/problem/view/IZhO18_segments

#include<bits/stdc++.h>
const int N = 2e5 + 5;
const int MAGIC = 1001;
using namespace std;

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

vector <segment> mv;
int n, t, L[N], R[N], ans, cnt, cur;
int l_sort[N], r_sort[N], l_nosort[N], r_nosort[N], p[N], num;
bool ck[N];

int bsearch(int l, int r, int k){
    while (l != r){
        int mid = (l + r) >> 1;
        if (r_nosort[mid] - l_nosort[mid] + 1 >= k) r = mid;
        else l = mid + 1;
    }
    if (r_nosort[l] - l_nosort[l] + 1 < k) return l + 1;
    return l;
}

void get_L(int pos, int k){
    int Max = (pos / MAGIC + 1) * MAGIC;
    for (int i = pos; i < min(Max, cnt); i++) if (r_nosort[i] < k) ans--;
    for (int i = Max; i < cnt; i += MAGIC){
        int x = i, y = min(i + MAGIC, cnt);
        int val = lower_bound(r_sort+x, r_sort+y, k) - r_sort - x;
        ans -= val;
    }
}

void get_R(int pos, int k){
    int Max = (pos / MAGIC + 1) * MAGIC;
    for (int i = pos; i < min(Max, cnt); i++) if (l_nosort[i] > k) ans--;
    for (int i = Max; i < cnt; i += MAGIC){
        int x = i, y = min(i + MAGIC, cnt);
        int val = y - (upper_bound(l_sort+x, l_sort+y, k) - l_sort);
        ans -= val;
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> t;
    if (n > 5000) return 0;
    while (n--){
        if (mv.size() == 1){
            cnt = 0; mv.clear();
            for (int i = 1; i < N; i++) if (ck[i]) p[cnt++] = i;
            sort(p, p+cnt, [](int x, int y){return (R[x] - L[x]) < (R[y] - L[y]);});
            for (int i = 0; i < cnt; i++) l_sort[i] = l_nosort[i] = L[p[i]];
            for (int i = 0; i < cnt; i++) r_sort[i] = r_nosort[i] = R[p[i]];
            for (int i = 0; i < cnt; i += MAGIC){
                int x = i, y = min(i + MAGIC, cnt);
                sort(l_sort+x, l_sort+y);
                sort(r_sort+x, r_sort+y);
            }
        }
        int type, l, r, id, k;
        cin >> type;
        if (type == 1){
            num++; id = ++cur;
            cin >> l >> r;
            l ^= (t * ans); r ^= (t * ans); if (r < l) swap(l, r);
            ck[id] = true;
            L[id] = l; R[id] = r;
            mv.push_back({l, r, 1});
        }
        if (type == 2){
            num--;
            cin >> id;
            ck[id] = false;
            mv.push_back({L[id], R[id], -1});
        }
        if (type == 3){
            cin >> l >> r >> k;
            l ^= (t * ans); r ^= (t * ans); if (r < l) swap(l, r);
            if (r - l + 1 < k){
                ans = 0; cout << ans << "\n";
                continue;
            }
            ans = num;
            if (cnt > 0){
                int pos = bsearch(0, cnt-1, k);
                ans -= pos;
                get_L(pos, l + k - 1);
                get_R(pos, r - k + 1);
            }
            for (int i = 0; i < mv.size(); i++){
                int x = max(mv[i].l, l), y = min(mv[i].r, r);
                if (y - x + 1 < k) ans -= mv[i].id;
            }
            cout <<  ans << "\n";
        }
    }
}

Compilation message

segments.cpp: In function 'int main()':
segments.cpp:94:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < mv.size(); i++){
                               ^

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 597 ms 808 KB Output is correct
4 Correct 635 ms 808 KB Output is correct
5 Correct 2244 ms 896 KB Output is correct
6 Correct 1916 ms 972 KB Output is correct
7 Correct 971 ms 972 KB Output is correct
8 Correct 2157 ms 972 KB Output is correct
9 Correct 2063 ms 972 KB Output is correct
10 Correct 2911 ms 1088 KB Output is correct
11 Correct 987 ms 1088 KB Output is correct
12 Correct 987 ms 1088 KB Output is correct
13 Correct 2856 ms 1088 KB Output is correct
14 Correct 1992 ms 1088 KB Output is correct
15 Correct 626 ms 1088 KB Output is correct
16 Correct 653 ms 1088 KB Output is correct
17 Correct 1399 ms 1088 KB Output is correct
18 Correct 2708 ms 1088 KB Output is correct
19 Correct 1425 ms 1088 KB Output is correct
20 Correct 1530 ms 1088 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 1088 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 597 ms 808 KB Output is correct
4 Correct 635 ms 808 KB Output is correct
5 Correct 2244 ms 896 KB Output is correct
6 Correct 1916 ms 972 KB Output is correct
7 Correct 971 ms 972 KB Output is correct
8 Correct 2157 ms 972 KB Output is correct
9 Correct 2063 ms 972 KB Output is correct
10 Correct 2911 ms 1088 KB Output is correct
11 Correct 987 ms 1088 KB Output is correct
12 Correct 987 ms 1088 KB Output is correct
13 Correct 2856 ms 1088 KB Output is correct
14 Correct 1992 ms 1088 KB Output is correct
15 Correct 626 ms 1088 KB Output is correct
16 Correct 653 ms 1088 KB Output is correct
17 Correct 1399 ms 1088 KB Output is correct
18 Correct 2708 ms 1088 KB Output is correct
19 Correct 1425 ms 1088 KB Output is correct
20 Correct 1530 ms 1088 KB Output is correct
21 Incorrect 1 ms 1088 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 597 ms 808 KB Output is correct
4 Correct 635 ms 808 KB Output is correct
5 Correct 2244 ms 896 KB Output is correct
6 Correct 1916 ms 972 KB Output is correct
7 Correct 971 ms 972 KB Output is correct
8 Correct 2157 ms 972 KB Output is correct
9 Correct 2063 ms 972 KB Output is correct
10 Correct 2911 ms 1088 KB Output is correct
11 Correct 987 ms 1088 KB Output is correct
12 Correct 987 ms 1088 KB Output is correct
13 Correct 2856 ms 1088 KB Output is correct
14 Correct 1992 ms 1088 KB Output is correct
15 Correct 626 ms 1088 KB Output is correct
16 Correct 653 ms 1088 KB Output is correct
17 Correct 1399 ms 1088 KB Output is correct
18 Correct 2708 ms 1088 KB Output is correct
19 Correct 1425 ms 1088 KB Output is correct
20 Correct 1530 ms 1088 KB Output is correct
21 Incorrect 1 ms 1088 KB Output isn't correct
22 Halted 0 ms 0 KB -