Submission #1109888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1109888		Zero_OP	Trampoline (info1cup20_trampoline)	C++14	23 / 100	107 ms	21732 KiB

trampoline

#include <bits/stdc++.h>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int R, C, N;
    cin >> R >> C >> N;

    struct point{
        int x, y;
    };

    vector<point> points(N);
    for(int i = 0; i < N; ++i){
        cin >> points[i].x >> points[i].y;
    }

    int T;
    cin >> T;

    struct route{
        point s, t;
    };

    vector<route> routes(T);
    for(int i = 0; i < T; ++i){
        cin >> routes[i].s.x >> routes[i].s.y >> routes[i].t.x >> routes[i].t.y;
    }

    vector<bool> answer(T, true);
    for(int i = 0; i < T; ++i){
        if(routes[i].s.x > routes[i].t.x || routes[i].s.y > routes[i].t.y){
            //degenerate case
            answer[i] = false;
        }
    }

    vector<vector<int>> level(251);
    for(int i = 0; i < N; ++i){
        level[points[i].x].push_back(points[i].y);
    }

    for(int i = 1; i <= 250; ++i){
        sort(level[i].begin(), level[i].end());
        level[i].erase(unique(level[i].begin(), level[i].end()), level[i].end());
        level[i].push_back(251);
    }

    for(int i = 0; i < T; ++i) if(answer[i]){
        int x = routes[i].s.x, y = routes[i].s.y;
        while(x < routes[i].t.x){
            auto it = lower_bound(level[x].begin(), level[x].end(), y);
            if(it == level[x].end()){
                answer[i] = false;
                break;
            }

            ++x;
            y = *it;
        }

        if(answer[i] && y > routes[i].t.y){ answer[i] = false; }
    }

    for(int i = 0; i < T; ++i){
        cout << (answer[i] ? "Yes\n" : "No\n");
    }

    return 0;
}

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