oj.uz

답안 #42810

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
42810 2018-03-04T13:13:32 Z minhtung0404 Segments (IZhO18_segments) C++14
0 / 100
 2308 ms 7132 KB 
//https://oj.uz/problem/view/IZhO18_segments

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

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

vector <segment> mv;
set <int> ms;
int n, t, L[N], R[N], ans, cnt;
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[pos] < 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[pos] > 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;
    for (int i = 1; i <= n; i++) ms.insert(i);
    while (n--){
        if (n % MAGIC == 0){
            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;
        cin >> type;
        if (type == 1){
            num++;
            int l, r, id; cin >> l >> r;
            l ^= (t * ans); r ^= (t * ans); if (r < l) swap(l, r);
            id = *(ms.begin()); ms.erase(ms.begin()); ck[id] = true;
            L[id] = l; R[id] = r;
            mv.push_back({l, r, 1});
        }
        if (type == 2){
            num--;
            int id ;cin >> id;
            ck[id] = false;
            ms.insert(id);
            mv.push_back({L[id], R[id], -1});
        }
        if (type == 3){
            int l, r, k; 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:96:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int i = 0; i < mv.size(); i++){
                               ^

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Incorrect 9 ms 936 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 2308 ms 7132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1010 ms 7132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 959 ms 7132 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Incorrect 9 ms 936 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 2 ms 372 KB Output is correct
3 Incorrect 9 ms 936 KB Output isn't correct
4 Halted 0 ms 0 KB -