oj.uz

Submission #603238

# Submission time Handle Problem Language Result Execution time Memory
603238 2022-07-23T17:57:17 Z peuch Event Hopping (BOI22_events) C++17
0 / 100
 217 ms 13144 KB 
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e5 + 10;
const int MAXK = 22;

int n, q;

struct interval{
    int l, r, id;
    interval (int _l = 0, int _r = 0){
        l = _l;
        r = _r;
        id = 0;
    }
    void scan(int _id){
        scanf("%d %d", &l, &r);
        id = _id;
    }
    bool operator < (interval x){
        if(r == x.r) return l < x.l;
        return r < x.r;
    }
}v[MAXN], ori[MAXN];

int dp[MAXN][MAXK];

int getDP(int i, int j){
    if(dp[i][j] != 0) return dp[i][j];
    return dp[i][j] = getDP(getDP(i, j - 1), j - 1);
}

int main(){
    scanf("%d %d", &n, &q);
    for(int i = 1; i <= n; i++){
        v[i].scan(i);
        ori[i] = v[i];
    }

    sort(v + 1, v + 1 + n);

    vector<interval > pilha;
    for(int i = 1; i <= n; i++){
        while(!pilha.empty() && pilha.back().l >= v[i].l)
            pilha.pop_back();
        pilha.push_back(v[i]);
        int k = lower_bound(pilha.begin(), pilha.end(), interval(-1, v[i].l)) - pilha.begin();
        dp[v[i].id][0] = pilha[k].id;
    }

    for(int i = 1; i <= q; i++){
        int a, b;
        scanf("%d %d", &a, &b);
        if(a == b){
            printf("0\n");
            continue;
        }
        if(ori[b].r < ori[a].r){
            printf("impossible\n");
            continue;
        }
        if(ori[a].r >= ori[b].l && ori[a].r >= ori[b].r){
            assert(false);
            printf("1\n");
            continue;
        }
        int ans = 0;
        for(int k = MAXK - 1; k >= 0; k--){
            int viz = getDP(b, k);
            if(ori[viz].l <= ori[a].r) continue;
            b = viz;
            ans += (1 << k);
        }
        if(getDP(b, 0) == b){
            printf("impossible\n");
            continue;
        }
        ans += 2;
        printf("%d\n", ans);
    }
}

Compilation message

events.cpp: In function 'int main()':
events.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d %d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~
events.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   53 |         scanf("%d %d", &a, &b);
      |         ~~~~~^~~~~~~~~~~~~~~~~
events.cpp: In member function 'void interval::scan(int)':
events.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d %d", &l, &r);
      |         ~~~~~^~~~~~~~~~~~~~~~~
events.cpp: In function 'int main()':
events.cpp:29:15: warning: array subscript -1 is below array bounds of 'int [22]' [-Warray-bounds]
   29 |     if(dp[i][j] != 0) return dp[i][j];
      |        ~~~~~~~^
events.cpp:29:15: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   29 |     if(dp[i][j] != 0) return dp[i][j];
      |        ~~~~~~~^
events.cpp:30:19: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   30 |     return dp[i][j] = getDP(getDP(i, j - 1), j - 1);
      |            ~~~~~~~^
events.cpp:29:15: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   29 |     if(dp[i][j] != 0) return dp[i][j];
      |        ~~~~~~~^
events.cpp:30:19: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   30 |     return dp[i][j] = getDP(getDP(i, j - 1), j - 1);
      |            ~~~~~~~^
events.cpp:30:19: warning: array subscript -1 is below array bounds of 'int [22]' [-Warray-bounds]
   30 |     return dp[i][j] = getDP(getDP(i, j - 1), j - 1);
      |            ~~~~~~~^
events.cpp:29:15: warning: array subscript -1 is below array bounds of 'int [22]' [-Warray-bounds]
   29 |     if(dp[i][j] != 0) return dp[i][j];
      |        ~~~~~~~^
events.cpp:29:15: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   29 |     if(dp[i][j] != 0) return dp[i][j];
      |        ~~~~~~~^
events.cpp:30:19: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   30 |     return dp[i][j] = getDP(getDP(i, j - 1), j - 1);
      |            ~~~~~~~^
events.cpp:29:15: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   29 |     if(dp[i][j] != 0) return dp[i][j];
      |        ~~~~~~~^
events.cpp:30:19: warning: array subscript -2 is below array bounds of 'int [22]' [-Warray-bounds]
   30 |     return dp[i][j] = getDP(getDP(i, j - 1), j - 1);
      |            ~~~~~~~^
events.cpp:30:19: warning: array subscript -1 is below array bounds of 'int [22]' [-Warray-bounds]
   30 |     return dp[i][j] = getDP(getDP(i, j - 1), j - 1);
      |            ~~~~~~~^

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 91 ms 13124 KB Output is correct
3 Correct 132 ms 13144 KB Output is correct
4 Incorrect 197 ms 13028 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

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

Subtask #3
0 / 15.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 79 ms 13100 KB Output is correct
2 Correct 149 ms 13120 KB Output is correct
3 Incorrect 217 ms 13116 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 91 ms 13124 KB Output is correct
3 Correct 132 ms 13144 KB Output is correct
4 Incorrect 197 ms 13028 KB Output isn't correct
5 Halted 0 ms 0 KB -