Submission #426828

#	Time	Username	Problem	Language	Result	Execution time	Memory
426828		tqbfjotld	Trampoline (info1cup20_trampoline)	C++14	100 / 100	481 ms	30144 KiB

trampoline

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

vector<pair<int,int> > items;
int decomp[200005][20];

int main(){
    int R,C,n;
    scanf("%d%d%d",&R,&C,&n);
    for (int x = 0; x<n; x++){
        int a,b;
        scanf("%d%d",&a,&b);
        items.push_back({a,b});
    }
    sort(items.begin(),items.end());
    for (int x = 0; x<n; x++){
        int num = lower_bound(items.begin(),items.end(),make_pair(items[x].first+1,items[x].second))-items.begin();
        if (num==n) decomp[x][0] = n;
        else if (items[num].first!=items[x].first+1){
            decomp[x][0] = n;
        }
        else{
            decomp[x][0] = num;
        }
    }
    decomp[n][0] = n;
    for (int x = 1; x<20; x++){
        for (int y = 0; y<=n; y++){
            decomp[y][x] = decomp[decomp[y][x-1]][x-1];
        }
    }
    int q;
    scanf("%d",&q);
    for (int x = 0; x<q; x++){
        int a,b,c,d;
        scanf("%d%d%d%d",&a,&b,&c,&d);
        if (a>c || b>d){
            printf("No\n");
            continue;
        }
        if (a==c){
            printf("Yes\n");
            continue;
        }
        int num = lower_bound(items.begin(),items.end(),make_pair(a,b))-items.begin();
        if (items[num].first!=a){
            printf("No\n");
            continue;
        }
        int diff = c-a-1;
        for (int x = 0; x<20; x++){
            if (diff&(1<<x)){
                num = decomp[num][x];
            }
        }
        if (num==n){
            printf("No\n");
            continue;
        }
        if (items[num].second>d){
            printf("No\n");
            continue;
        }
        printf("Yes\n");

    }
}

Compilation message (stderr)

trampoline.cpp: In function 'int main()':
trampoline.cpp:9:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
    9 |     scanf("%d%d%d",&R,&C,&n);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
trampoline.cpp:12:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 |         scanf("%d%d",&a,&b);
      |         ~~~~~^~~~~~~~~~~~~~
trampoline.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d",&q);
      |     ~~~~~^~~~~~~~~
trampoline.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         scanf("%d%d%d%d",&a,&b,&c,&d);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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