Submission #603239

#	Time	Username	Problem	Language	Result	Execution time	Memory
603239		peuch	Event Hopping (BOI22_events)	C++17	100 / 100	254 ms	16672 KiB

events

#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){
            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 (stderr)

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: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: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: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30