oj.uz

Submission #580368

# Submission time Handle Problem Language Result Execution time Memory
580368 2022-06-21T07:16:11 Z 반딧불(#8355) Event Hopping (BOI22_events) C++17
30 / 100
 162 ms 13204 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

struct Range{
    int l, r, idx;
    Range(){}
    Range(int l, int r, int idx): l(l), r(r), idx(idx){}
    bool operator<(const Range &nxt)const{
        return r<nxt.r;
    }
};

struct dat{
    int x, v, idx;
    dat(){}
    dat(int x, int v, int idx): x(x), v(v), idx(idx){}
    bool operator<(const dat &r)const{
        if(x!=r.x) return x<r.x;
        return v>r.v;
    }
};

int n, q;
Range arr[100002];

void input();
void process();
void output();

int main(){
    input();
    process();
    output();
}

void input(){
    scanf("%d %d", &n, &q);
    for(int i=1; i<=n; i++){
        scanf("%d %d", &arr[i].l, &arr[i].r);
        arr[i].idx = i;
    }
}

int nxt[100002];
int sps[100002][20];
int idx[100002];

void process(){
    sort(arr+1, arr+n+1);
    for(int i=1; i<=n; i++) idx[arr[i].idx] = i;

    vector<dat> vec;
    for(int i=n; i>=1; i--){
        vec.push_back(dat(arr[i].r, arr[i].l, i));
    }
    sort(vec.rbegin(), vec.rend());
    vector<dat> vec2;
    for(auto x: vec){
        if(vec2.empty() || vec2.back().v > x.v) vec2.push_back(x);
    }
    reverse(vec2.begin(), vec2.end());
    for(int i=1; i<=n; i++){
        nxt[i] = lower_bound(vec2.begin(), vec2.end(), dat(arr[i].l, INT_MAX, 0))->idx;
        if(arr[nxt[i]].r < arr[i].l || arr[nxt[i]].r > arr[i].r) nxt[i] = i;
    }


    for(int i=1; i<=n; i++) sps[i][0] = nxt[i];
    for(int d=1; d<20; d++) for(int i=1; i<=n; i++) sps[i][d] = sps[sps[i][d-1]][d-1];
}

void output(){
    while(q--){
        int l, r;
        scanf("%d %d", &l, &r);
        l = idx[l], r = idx[r];
        if(l==r) puts("0");
        else if(arr[r].r < arr[l].r) puts("impossible");
        else{
            int ans = 0;
            for(int d=19; d>=0; d--){
                if(arr[sps[r][d]].l > arr[l].r) ans += (1<<d), r = sps[r][d];
            }
            if(ans > n) puts("impossible");
            else printf("%d\n", ans+(arr[r].l <= arr[l].r && arr[l].r <= arr[r].r ? 1 : 2));
        }
    }
}

Compilation message

events.cpp: In function 'void input()':
events.cpp:40:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:42:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   42 |         scanf("%d %d", &arr[i].l, &arr[i].r);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
events.cpp: In function 'void output()':
events.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 92 ms 12496 KB Output is correct
3 Correct 104 ms 12528 KB Output is correct
4 Correct 115 ms 12496 KB Output is correct
5 Correct 107 ms 12384 KB Output is correct
6 Correct 96 ms 12220 KB Output is correct
7 Correct 95 ms 12260 KB Output is correct
8 Correct 89 ms 11300 KB Output is correct
9 Correct 100 ms 12772 KB Output is correct
10 Correct 138 ms 13204 KB Output is correct
11 Correct 138 ms 12920 KB Output is correct
12 Correct 84 ms 12772 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Incorrect 1 ms 340 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 12488 KB Output is correct
2 Correct 90 ms 12488 KB Output is correct
3 Correct 99 ms 12456 KB Output is correct
4 Correct 99 ms 12532 KB Output is correct
5 Correct 131 ms 12492 KB Output is correct
6 Correct 137 ms 12564 KB Output is correct
7 Correct 125 ms 12520 KB Output is correct
8 Correct 162 ms 12496 KB Output is correct
9 Correct 66 ms 12468 KB Output is correct
10 Correct 96 ms 12528 KB Output is correct
11 Correct 95 ms 12556 KB Output is correct
12 Correct 102 ms 12488 KB Output is correct

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 92 ms 12496 KB Output is correct
3 Correct 104 ms 12528 KB Output is correct
4 Correct 115 ms 12496 KB Output is correct
5 Correct 107 ms 12384 KB Output is correct
6 Correct 96 ms 12220 KB Output is correct
7 Correct 95 ms 12260 KB Output is correct
8 Correct 89 ms 11300 KB Output is correct
9 Correct 100 ms 12772 KB Output is correct
10 Correct 138 ms 13204 KB Output is correct
11 Correct 138 ms 12920 KB Output is correct
12 Correct 84 ms 12772 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Incorrect 1 ms 340 KB Output isn't correct
18 Halted 0 ms 0 KB -