Submission #920917

#	Time	Username	Problem	Language	Result	Execution time	Memory
920917		salmon	Trampoline (info1cup20_trampoline)	C++14	100 / 100	1080 ms	73296 KiB

trampoline

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

int R,C;
map<int,set<int>> mep;
pair<int,int> tramp[200100];
map<pair<int,int>,int> de;
int N;
int T;
int h,h1;
int parent[200100][30];
int e,e1;

int main(){
    scanf(" %d",&R);
    scanf(" %d",&C);

    scanf(" %d",&N);

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

    for(int i = 0; i < N; i++){
        scanf(" %d",&h);
        scanf(" %d",&h1);
        mep[h].insert(h1);
        de[{h,h1}] = i;
        tramp[i] = {h,h1};
    }

    for(int i = 0; i < N; i++){
        if(mep.find(tramp[i].first + 1) != mep.end()){
            if(mep[tramp[i].first + 1].lower_bound(tramp[i].second) != mep[tramp[i].first + 1].end()){
                parent[i][0] = de[{tramp[i].first + 1, *mep[tramp[i].first + 1].lower_bound(tramp[i].second)}] ;
            }
        }
    }

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

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

    scanf(" %d",&T);

    for(int i = 0; i < T; i++){
        scanf(" %d",&h);
        scanf(" %d",&h1);

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

        if(e < h || e1 < h1){
            printf("No\n");
            continue;
        }

        if(h == e){
            printf("Yes\n");
        }
        else{
            if(mep.find(h) == mep.end()){
                printf("No\n");
            }
            else{
                if(mep[h].lower_bound(h1) == mep[h].end()){
                    printf("No\n");
                    continue;
                }
                int j = *mep[h].lower_bound(h1);
                j = de[{h,j}];

                int i = 25;
                while(i != -1){
                    if(parent[j][i] != -1 && tramp[parent[j][i]].first <= e - 1){
                        j = parent[j][i];
                    }
                    i--;
                }
                //printf("%d\n",tramp[j].first);
                if(tramp[j].first == e - 1){
                    if(tramp[j].second <= e1) printf("Yes\n");
                    else printf("No\n");
                }
                else{
                    printf("No\n");
                }
            }
        }
    }
}

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf(" %d",&R);
      |     ~~~~~^~~~~~~~~~
trampoline.cpp:16:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |     scanf(" %d",&C);
      |     ~~~~~^~~~~~~~~~
trampoline.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf(" %d",&N);
      |     ~~~~~^~~~~~~~~~
trampoline.cpp:27:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   27 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
trampoline.cpp:28:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   28 |         scanf(" %d",&h1);
      |         ~~~~~^~~~~~~~~~~
trampoline.cpp:57:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |     scanf(" %d",&T);
      |     ~~~~~^~~~~~~~~~
trampoline.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf(" %d",&h);
      |         ~~~~~^~~~~~~~~~
trampoline.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf(" %d",&h1);
      |         ~~~~~^~~~~~~~~~~
trampoline.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |         scanf(" %d",&e);
      |         ~~~~~^~~~~~~~~~
trampoline.cpp:64:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |         scanf(" %d",&e1);
      |         ~~~~~^~~~~~~~~~~

• Subtask 1: 23 / 23
• Subtask 2: 20 / 20
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 27 / 27