Submission #889375

#	Time	Username	Problem	Language	Result	Execution time	Memory
889375		salmon	Railway Trip 2 (JOI22_ho_t4)	C++14	100 / 100	1893 ms	353620 KiB

Main

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

int N;
int M,Q;
int A,B;
int K;
int lt[100100];
int rt[100100];
int l[100100][30];
int r[100100][30];

struct node{

    int s,e,m;
    node *l,*r;
    int le,ri;
    int d;

    node(int S, int E, int D){
        s = S;
        e = E;
        m = (s + e)/2;
        d = D;

        if(s == e){
            le = ::l[s][d];
            ri = ::r[s][d];
        }
        else{
            l = new node(s,m,d);
            r = new node(m + 1,e,d);

            le = min(l -> le, r -> le);
            ri = max(l -> ri, r -> ri);
        }
    }


    pair<int,int> query(int S, int E){
        if(S <= s && e <= E){
            return make_pair(le,ri);
        }

        pair<int,int> ii = make_pair(S,E);
        pair<int,int> ii1;

        if(S <= m){
            ii1 = l -> query(S,E);

            ii.first = min(ii.first, ii1.first);
            ii.second = max(ii.second,ii1.second);
        }
        if(m < E){
            ii1 = r -> query(S,E);

            ii.first = min(ii.first, ii1.first);
            ii.second = max(ii.second, ii1.second);
        }

        return ii;
    }
} *root[30];

int main(){

    scanf(" %d",&N);
    scanf(" %d",&K);
    scanf(" %d",&M);

    for(int i = 1; i <= N; i++){
        rt[i] = i;
        lt[i] = i;
    }

    for(int i = 1; i <= M; i++){
        scanf(" %d",&A);
        scanf(" %d",&B);

        if(B > A){
            rt[A] = max(rt[A],B);
        }
        else if(B < A){
            lt[A] = min(lt[A],B);
        }
    }

    deque<pair<int,int>> dq;

    for(int i = 1; i <= N; i++){

        while(!dq.empty() && dq.front().first == i){
            dq.pop_front();
        }

        while(!dq.empty() && dq.back().second <= rt[i]){
            dq.pop_back();
        }

        dq.push_back(make_pair(i + K,rt[i]) );

        r[i][0] = dq.front().second;
    }

    dq.clear();

    for(int i = N; i >= 1; i--){
        while(!dq.empty() && dq.front().first == i){
            dq.pop_front();
        }

        while(!dq.empty() && dq.back() .second >= lt[i]){
            dq.pop_back();
        }

        dq.push_back(make_pair(i - K,lt[i]));

        l[i][0] = dq.front().second;
    }

    root[0] = new node(1,N,0);


    for(int j = 1; j <= 25; j++){
        for(int i = 1; i <= N; i++){
            pair<int,int> ii = root[j - 1] -> query(i,i);

            ii = root[j - 1] -> query(ii.first,ii.second);

            l[i][j] = ii.first;
            r[i][j] = ii.second;
        }

        root[j] = new node(1,N,j);
    }

    scanf(" %d",&Q);

    for(int i = 0; i < Q; i++){
        scanf(" %d",&A);
        scanf(" %d",&B);

        int sum = 0;
        pair<int,int> ii = root[25] -> query(A,A);
        pair<int,int> temp;

        if(ii.first > B || B > ii.second){
            printf("-1\n");
        }
        else{
            ii = make_pair(A,A);
            temp = make_pair(A,A);

            for(int i = 25; i >= 0; i--){
                temp = root[i] -> query(ii.first, ii.second);

                if(temp.first > B || B > temp.second){
                    ii = temp;
                    sum += (1<<i);
                }
            }

            printf("%d\n",sum + 1);

        }
    }
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:67:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   67 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
Main.cpp:68:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |     scanf(" %d",&K);
      |     ~~~~~^~~~~~~~~~
Main.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |     scanf(" %d",&M);
      |     ~~~~~^~~~~~~~~~
Main.cpp:77:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |         scanf(" %d",&A);
      |         ~~~~~^~~~~~~~~~
Main.cpp:78:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   78 |         scanf(" %d",&B);
      |         ~~~~~^~~~~~~~~~
Main.cpp:137:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  137 |     scanf(" %d",&Q);
      |     ~~~~~^~~~~~~~~~
Main.cpp:140:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  140 |         scanf(" %d",&A);
      |         ~~~~~^~~~~~~~~~
Main.cpp:141:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  141 |         scanf(" %d",&B);
      |         ~~~~~^~~~~~~~~~

• Subtask 1: 8 / 8
• Subtask 2: 8 / 8
• Subtask 3: 11 / 11
• Subtask 4: 25 / 25
• Subtask 5: 35 / 35
• Subtask 6: 13 / 13