oj.uz

Submission #1109888

# Submission time Handle Problem Language Result Execution time Memory
1109888 2024-11-08T02:43:28 Z Zero_OP Trampoline (info1cup20_trampoline) C++14
23 / 100
 107 ms 21732 KB 
#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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 592 KB 200 token(s): yes count is 21, no count is 179
2 Correct 3 ms 592 KB 200 token(s): yes count is 70, no count is 130
3 Correct 2 ms 592 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 25 ms 5712 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 94 ms 21732 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1104 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 107 ms 21576 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -