oj.uz

Submission #580362

# Submission time Handle Problem Language Result Execution time Memory
580362 2022-06-21T07:09:32 Z 반딧불(#8355) Event Hopping (BOI22_events) C++17
0 / 100
 167 ms 12864 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+(nxt[r]==l ? 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 88 ms 12472 KB Output is correct
3 Correct 88 ms 12864 KB Output is correct
4 Correct 137 ms 12864 KB Output is correct
5 Correct 100 ms 12656 KB Output is correct
6 Correct 92 ms 12688 KB Output is correct
7 Correct 97 ms 12476 KB Output is correct
8 Incorrect 77 ms 11880 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 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 0 ms 212 KB Output is correct
2 Correct 0 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 0 ms 212 KB Output is correct
2 Correct 0 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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 106 ms 12480 KB Output is correct
2 Correct 87 ms 12520 KB Output is correct
3 Correct 99 ms 12468 KB Output is correct
4 Correct 91 ms 12480 KB Output is correct
5 Correct 126 ms 12508 KB Output is correct
6 Incorrect 167 ms 12640 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 88 ms 12472 KB Output is correct
3 Correct 88 ms 12864 KB Output is correct
4 Correct 137 ms 12864 KB Output is correct
5 Correct 100 ms 12656 KB Output is correct
6 Correct 92 ms 12688 KB Output is correct
7 Correct 97 ms 12476 KB Output is correct
8 Incorrect 77 ms 11880 KB Output isn't correct
9 Halted 0 ms 0 KB -