oj.uz

답안 #389726

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
389726 2021-04-14T12:12:25 Z georgerapeanu Event Hopping 2 (JOI21_event2) C++11
32 / 100
 110 ms 38724 KB 
#include <bits/stdc++.h>

using namespace std;

const int LGMAX = 17;
const int NMAX = 1e5;

int n,k;
map<int,int> to_norm;
int skip_list[LGMAX + 1][NMAX + 5];
pair<int,int> v[NMAX + 5];
int closest_endpoint[2 * NMAX + 5];

int get_segment_count(int l,int r){
    if(l > r){
        return 0;
    }
    int ans = 0;
    for(int h = LGMAX;h >= 0;h--){
        if(skip_list[h][l] != 0 && skip_list[h][l] <= r + 1){
            ans += (1 << h);
            l = skip_list[h][l];
        }
    }
    return ans;
}

int aib[2 * NMAX + 5];

void update(int pos){
    for(;pos <= 2 * n + 3;pos += (-pos) & pos){
        aib[pos] ^= 1;
    }
}

int query(int pos){
    int ans = 0;

    for(;pos;pos -= (-pos) & pos){
        ans ^= aib[pos];
    }

    return ans;
}

set<int> pos; 

int main(){

   
    scanf("%d %d",&n,&k);

    for(int i = 1;i <= n;i++){
        scanf("%d %d",&v[i].first,&v[i].second);
        v[i].second--;
        to_norm[v[i].first] = 1;
        to_norm[v[i].second] = 1;
    }

    int lst = 0;

    for(auto &it:to_norm){
        it.second = ++lst;
    }

    for(int i = 1;i <= lst + 1;i++){
        closest_endpoint[i] = 1e9;
    }

    for(int i = 1;i <= n;i++){
        v[i].first = to_norm[v[i].first];
        v[i].second = to_norm[v[i].second];
        closest_endpoint[v[i].first] = min(closest_endpoint[v[i].first],v[i].second);
    }

    for(int i = lst;i;i--){
        skip_list[0][i] = skip_list[0][i + 1];
        if(closest_endpoint[i] != 1e9 && (skip_list[0][i] == 0 || closest_endpoint[i] + 1 < skip_list[0][i])){
            skip_list[0][i] = closest_endpoint[i] + 1;
        }
    }

    for(int h = 1;h <= LGMAX;h++){
        for(int i = 1;i <= lst;i++){
            skip_list[h][i] = skip_list[h - 1][skip_list[h - 1][i]];
        }
    }

    pos.insert(0);
    pos.insert(2 * n + 3);

    int ans = get_segment_count(1,2 * n + 2);
    if(ans < k){
        printf("-1\n");
        return 0;
    }

    for(int i = 1;i <= n;i++){
        set<int> :: iterator it;
        it = pos.lower_bound(v[i].first);
        if(*it <= v[i].second || query(v[i].first)){
            continue;
        }
        int r = *it - 1;
        it--;
        int l = *it + 1;
        int local_ans = ans - get_segment_count(l,r) + get_segment_count(l,v[i].first - 1) + get_segment_count(v[i].second + 1,r);
        if(k > 0 && local_ans >= k - 1){
            k--;
            ans = local_ans;
            printf("%d\n",i);
            pos.insert(v[i].first);
            pos.insert(v[i].second);
            update(v[i].first);
            update(v[i].second + 1);
        }
    }

    return 0;
}

Compilation message

event2.cpp: In function 'int main()':
event2.cpp:51:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   51 |     scanf("%d %d",&n,&k);
      |     ~~~~~^~~~~~~~~~~~~~~
event2.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   54 |         scanf("%d %d",&v[i].first,&v[i].second);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Runtime error 110 ms 38724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
1.0 / 1.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 304 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct

Subtask #3
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 1 ms 332 KB Output is correct
15 Correct 1 ms 332 KB Output is correct
16 Correct 1 ms 332 KB Output is correct
17 Correct 1 ms 332 KB Output is correct
18 Correct 1 ms 332 KB Output is correct
19 Correct 1 ms 332 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 332 KB Output is correct
22 Correct 1 ms 332 KB Output is correct
23 Correct 1 ms 304 KB Output is correct
24 Correct 1 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 4 ms 1228 KB Output is correct
29 Correct 4 ms 1228 KB Output is correct
30 Correct 4 ms 1228 KB Output is correct
31 Correct 4 ms 1228 KB Output is correct
32 Correct 4 ms 1216 KB Output is correct
33 Correct 4 ms 1100 KB Output is correct
34 Correct 4 ms 1080 KB Output is correct
35 Correct 7 ms 1448 KB Output is correct
36 Correct 6 ms 1376 KB Output is correct
37 Correct 6 ms 1336 KB Output is correct
38 Correct 4 ms 1100 KB Output is correct
39 Correct 8 ms 1356 KB Output is correct
40 Correct 6 ms 1380 KB Output is correct
41 Correct 6 ms 1336 KB Output is correct
42 Correct 4 ms 1100 KB Output is correct
43 Correct 5 ms 1228 KB Output is correct
44 Correct 5 ms 1228 KB Output is correct
45 Correct 5 ms 1228 KB Output is correct
46 Correct 4 ms 1080 KB Output is correct
47 Correct 5 ms 1176 KB Output is correct
48 Correct 4 ms 1228 KB Output is correct
49 Correct 4 ms 1228 KB Output is correct
50 Correct 5 ms 1100 KB Output is correct
51 Correct 4 ms 1212 KB Output is correct
52 Correct 4 ms 1228 KB Output is correct
53 Correct 6 ms 1228 KB Output is correct
54 Correct 4 ms 1100 KB Output is correct
55 Correct 5 ms 1484 KB Output is correct
56 Correct 5 ms 1472 KB Output is correct
57 Correct 5 ms 1484 KB Output is correct
58 Correct 5 ms 1484 KB Output is correct
59 Correct 5 ms 1484 KB Output is correct
60 Correct 5 ms 1484 KB Output is correct
61 Correct 5 ms 1484 KB Output is correct
62 Correct 5 ms 1356 KB Output is correct
63 Correct 5 ms 1356 KB Output is correct
64 Correct 3 ms 1100 KB Output is correct

Subtask #4
0 / 61.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Runtime error 110 ms 38724 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -