제출 #1127243

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1127243		salmon	Event Hopping (BOI22_events)	C++20	100 / 100	532 ms	145748 KiB

events

#include <bits/stdc++.h>
using namespace std;

int N;
int Q;
int parent[100100][30];
int l[100100];
int r[100100];
vector<pair<int,int>> slort;
vector<pair<int,int>> pop;
const int inf = 1.1e9;

struct node{

    int s,e,m;
    pair<int,int> v;

    node *l, *r;

    node(int S, int E){
        s = S;
        e = E;
        m = (s + e)/2;
        v = {inf,-1};

        if(s != e){
            l = NULL;
            r = NULL;
        }
    }

    pair<int,int> query(int S, int E){
        if(S <= s && e <= E) return v;

        pair<int,int> V = {inf,-1};

        if(l == NULL) return V;

        if(S <= m){
            V = min(V,l -> query(S,E));
        }
        if(m < E){
            V = min(V,r -> query(S,E));
        }

        return V;
    }

    void update(int i, int k, int in){
        if(s == e){
            v = min(v,{k,in});
            return;
        }

        if(l == NULL){
            l = new node(s,m);
            r = new node(m + 1,e);
        }

        if(i <= m){
            l -> update(i,k,in);
        }
        else{
            r -> update(i,k,in);
        }

        v = min(l -> v, r -> v);
    }

}*root;

int main(){

    scanf(" %d",&N);
    scanf(" %d",&Q);

    for(int i = 0; i < N; i++){
        scanf(" %d",&l[i]);
        scanf(" %d",&r[i]);

        slort.push_back({r[i],i});
        pop.push_back({l[i] - 1,i});
    }

    sort(slort.begin(),slort.end(),greater<pair<int,int>>() );
    sort(pop.begin(), pop.end(), greater<pair<int,int>>());

    int it = 0;
    pair<int,int> ii = {inf,-1};

    root = new node(0,inf);

    for(int i = 0; i < N; i++){
        while(it != N && pop[it].first >= slort[i].first){
            parent[pop[it].second][0] = (root -> query(0,r[pop[it].second]) ).second;
            it++;
        }

        root -> update(slort[i].first,l[slort[i].second],slort[i].second);
    }

    while(it != N){
        parent[pop[it].second][0] = (root -> query(0,r[pop[it].second]) ).second;
        it++;
    }

    for(int j = 1; j < 30; j++){
        for(int i = 0; i < N; i++){
            parent[i][j] = parent[parent[i][j - 1]][j - 1];
        }
    }

    /*for(int i = 0; i < N; i++){
        printf("%d ",parent[i][0]);
    }*/

    for(int i = 0; i < Q; i++){
        int s,e;

        scanf(" %d",&s);
        scanf(" %d",&e);

        s--;
        e--;

        if(s == e){
            printf("0\n");
            continue;
        }
        else if(r[s] > r[e]){
            printf("impossible\n");
            continue;
        }
        else if(r[s] >= l[e]){
            printf("1\n");
            continue;
        }

        int num = 0;
        int k = e;

        for(int j = 25; j >= 0; j--){
            if( l[parent[k][j]] > r[s] ){
                k = parent[k][j];
                num += (1<<j);
            }
        }

        num += 2;

        if(num >= N) printf("impossible\n");
        else printf("%d\n",num);
    }
}

컴파일 시 표준 에러 (stderr) 메시지

events.cpp: In function 'int main()':
events.cpp:74:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
events.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   75 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
events.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf(" %d",&l[i]);
      |         ~~~~~^~~~~~~~~~~~~
events.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   79 |         scanf(" %d",&r[i]);
      |         ~~~~~^~~~~~~~~~~~~
events.cpp:120:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  120 |         scanf(" %d",&s);
      |         ~~~~~^~~~~~~~~~
events.cpp:121:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  121 |         scanf(" %d",&e);
      |         ~~~~~^~~~~~~~~~

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