Submission #374672

#	Time	Username	Problem	Language	Result	Execution time	Memory
374672		Alex_tz307	Trampoline (info1cup20_trampoline)	C++17	100 / 100	543 ms	39660 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;

class coord {
    public:
        int x, y;

        bool operator < (const coord &A) const {
            if(x != A.x)
                return x < A.x;
            return y < A.y;
        }

        bool operator > (const coord &A) const {
            if(x != A.x)
                return x > A.x;
            return y > A.y;
        }
};

const int NMAX = 2e5 + 5;
int R, C, N, Q, ancestor[NMAX][32];
coord a[NMAX];

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    cin >> R >> C >> N;
    for(int i = 1; i <= N; ++i)
        cin >> a[i].x >> a[i].y;
    sort(a + 1, a + N + 1);
    for(int i = 2; i <= N; ++i) {
        int st = 1, dr = N, prv_line = a[i].x - 1, l = -1, r = -1;
        while(st <= dr) {
            int mid = (st + dr) >> 1;
            if(a[mid].x >= prv_line) {
                l = mid;
                dr = mid - 1;
            }
            else
                st = mid + 1;
        }
        st = 1, dr = N;
        while(st <= dr) {
            int mid = (st + dr) >> 1;
            if(a[mid].x <= prv_line) {
                r = mid;
                st = mid + 1;
            }
            else
                dr = mid - 1;
        }
        if(l == -1 || r == -1 || a[l].x != prv_line || a[r].x != prv_line)
            continue;
        int ans = -1;
        while(l <= r) {
            int mid = (l + r) >> 1;
            if(a[mid].y <= a[i].y) {
                ans = mid;
                l = mid + 1;
            }
            else
                r = mid - 1;
        }
        if(ans != -1)
            ancestor[i][0] = ans;
    }
    for(int level = 1; level < 31; ++level)
        for(int i = 1; i <= N; ++i)
            ancestor[i][level] = ancestor[ancestor[i][level - 1]][level - 1];
    cin >> Q;
    for(int q = 0; q < Q; ++q) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1 > x2 || y1 > y2) {
            cout << "No\n";
            continue;
        }
        if(x1 == x2) {
            cout << "Yes\n";
            continue;
        }
        --x2;
        int ans = -1, st = 1, dr = N;
        while(st <= dr) {
            int mid = (st + dr) >> 1;
            if(a[mid] > coord{x2, y2})
                dr = mid - 1;
            else {
                if(a[mid].x == x2)
                    ans = mid;
                st = mid + 1;
            }
        }
        if(ans == -1 || a[ans].y < y1 || a[ans].y > y2) {
            cout << "No\n";
            continue;
        }
        for(int level = 30; level >= 0; --level) {
            int father = ancestor[ans][level];
            if(a[father].x >= x1)
                ans = father;
        }
        if(a[ans].x == x1 && a[ans].y >= y1)
            cout << "Yes\n";
        else
            cout << "No\n";
    }
}

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