oj.uz

Submission #332225

# Submission time Handle Problem Language Result Execution time Memory
332225 2020-12-01T17:59:52 Z evpipis Trampoline (info1cup20_trampoline) C++11
0 / 100
 362 ms 37940 KB 
#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef pair<int, int> ii;

const int len = 2e5+5, lg = 30;
ii point[len];
int k, dp[len][lg];

int fir(int x, int y){
    int l = 1, r = k, ans = k+1;
    while (l <= r){
        int mid = (l+r)/2;
        if (point[mid] >= mp(x, y))
            ans = mid, r = mid-1;
        else
            l = mid+1;
    }

    if (ans == k+1 || point[ans].fi > x)
        return 0;
    return ans;
}

int main(){
    int n, m, q;
    scanf("%d %d %d", &n, &m, &k);

    for (int i = 1; i <= k; i++)
        scanf("%d %d", &point[i].fi, &point[i].se);
    point[0] = mp(len, len);

    sort(point+1, point+1+k);

    for (int i = 1; i <= k; i++)
        dp[i][0] = fir(point[i].fi, point[i].se);
    for (int j = 1; j < lg; j++)
        for (int i = 1; i <= k; i++)
            dp[i][j] = dp[dp[i][j-1]][j-1];

    scanf("%d", &q);
    while (q--){
        int x1, y1, x2, y2;
        scanf("%d %d %d %d", &x1, &y1, &x2, &y2);

        if (x1 > x2 || y1 > y2)
            printf("No\n");
        else if (x1 == x2)
            printf("Yes\n");
        else{
            int i = fir(x1, y1), dif = x2-x1-1;
            for (int j = 0; j < lg; j++)
                if (dif&(1<<j))
                    i = dp[i][j];

            if (point[i].se <= y2)
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:31:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   31 |     scanf("%d %d %d", &n, &m, &k);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   34 |         scanf("%d %d", &point[i].fi, &point[i].se);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
trampoline.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   45 |     scanf("%d", &q);
      |     ~~~~~^~~~~~~~~~
trampoline.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   48 |         scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 1644 KB expected NO, found YES [2nd token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 160 ms 27264 KB expected NO, found YES [1st token]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 297 ms 37880 KB expected NO, found YES [5147th token]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 1260 KB expected NO, found YES [59th token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 362 ms 37940 KB expected NO, found YES [23rd token]
2 Halted 0 ms 0 KB -