Submission #577669

#	Time	Username	Problem	Language	Result	Execution time	Memory
577669		patrikpavic2	Event Hopping (BOI22_events)	C++17	100 / 100	1325 ms	58904 KiB

events

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>

#define PB push_back

using namespace std;

const int N = 2e5 + 500;
const int OFF = (1 << 18);
const int LOG = 20;
const int INF = 0x3f3f3f3f;

int n, q, L[N], R[N], T[LOG][2 * OFF];
int dp[LOG][N], dobar[LOG][N];
vector < int > saz;

void build(int j){
    for(int i = OFF - 1; i ; i--)
        T[j][i] = min(T[j][2 * i], T[j][2 * i + 1]);
}

int query(int j, int i, int a, int b, int lo, int hi){
    if(lo <= a && b <= hi) return T[j][i];
    if(a > hi || b < lo) return INF;
    return min(query(j, 2 * i, a, (a + b) / 2, lo, hi), query(j, 2 * i + 1, (a + b) / 2 + 1, b, lo, hi));
}

int main(){
    memset(T, INF, sizeof(T));
    scanf("%d%d", &n, &q);
    for(int i = 0;i < n;i++){
        scanf("%d%d", L + i, R + i);
        saz.PB(L[i]); saz.PB(R[i]);
        dp[0][i] = L[i];
    }
    sort(saz.begin(), saz.end());
    saz.erase(unique(saz.begin(), saz.end()), saz.end());
    for(int i = 0;i < n;i++){
        L[i] = lower_bound(saz.begin(), saz.end(), L[i]) - saz.begin();
        R[i] = lower_bound(saz.begin(), saz.end(), R[i]) - saz.begin();
        dp[0][i] = L[i];
        dobar[0][i] = 1;
        T[0][OFF + R[i]] = min(T[0][OFF + R[i]], L[i]);
    }
    build(0);
    for(int j = 1;j < LOG;j++){
        for(int i = 0;i < n;i++){
            if(!dobar[j - 1][i]){
                dp[j][i] = dp[j - 1][i];
            }
            else{
                dp[j][i] = query(j - 1, 1, 0, OFF - 1, dp[j - 1][i], R[i]);
                if(dp[j][i] < dp[j - 1][i])
                    dobar[j][i] = 1;
            }
            T[j][OFF + R[i]] = min(T[j][OFF + R[i]], dp[j][i]);
         //   printf("dp[ %d ][ %d ] = %d\n", j, i, dp[j][i]);
        }
        build(j);
    }
    for(int i = 0;i < q;i++){
        int s, t; scanf("%d%d", &s, &t);
        s--; t--;
        if(R[s] > R[t] || dp[LOG - 1][t] > R[s]){
            printf("impossible\n");
            continue;
        }
        if(s == t){
            printf("0\n");
            continue;
        }
        if(R[s] >= L[t]){
            printf("1\n");
            continue;
        }
        int odg = 0, curL = L[t];
        for(int j = LOG - 1;j >= 0;j--){
            int nw = query(j, 1, 0, OFF - 1, curL, R[t]);
            if(nw > R[s] && nw < curL){
         //       printf("uzeo j = %d\n", j);
          //      printf("prije %d sad %d\n", curL, nw);
                odg += (1 << j);
                curL = nw;
            }
        }
        printf("%d\n", odg + 2);
    }
    return 0;
}

Compilation message (stderr)

events.cpp: In function 'int main()':
events.cpp:32:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |     scanf("%d%d", &n, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~
events.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         scanf("%d%d", L + i, R + i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~
events.cpp:64:24: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         int s, t; scanf("%d%d", &s, &t);
      |                   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30