oj.uz

Submission #845376

# Submission time Handle Problem Language Result Execution time Memory
845376 2023-09-06T13:23:27 Z M_W_13 Trampoline (info1cup20_trampoline) C++17
42 / 100
 2000 ms 12544 KB 
#include <iostream>
#include <vector>
using namespace std;
int r, c, n;
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> r >> c >> n;
    vector <vector <int>> zielone;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        zielone.push_back({});
        zielone[i].push_back(a);
        zielone[i].push_back(b);
    }
    int jaki[n];
    for (int i = 0; i < n; i++) {
        jaki[i] = -1;
        for (int j = 0; j < n; j++) {
            if (zielone[j][0] == zielone[i][0] + 1 && zielone[j][1] >= zielone[i][1]) {
                if (jaki[i] == -1) {
                    jaki[i] = j;
                }
                else {
                    if (zielone[j][1] < zielone[jaki[i]][1]) {
                        jaki[i] = j;
                    }
                }
            }
        }
    }
    int t;
    cin >> t;
    for (int pyt = 0; pyt < t; pyt++) {
        int x, y, x2, y2;
        cin >> x >> y >> x2 >> y2;
        int x_s = x;
        int a = -1, b = 1e9 + 7;
        int pole = -1;
        for (int i = 0; i < n; i++) {
            if (zielone[i][0] == x && zielone[i][1] >= y) {
                if (a == - 1 || zielone[i][1] < b) {
                    a = zielone[i][0];
                    b = zielone[i][1];
                    pole = i;
                }
            }
        }
        if (x == x2 && y <= y2) {
            cout << "Yes" << endl;
        }
        else if (a == -1) {
            cout << "No" << endl;
        }
        else {
            x = a + 1; y = b;
            while (x < x2 && y <= y2) {
                if (jaki[pole] == -1) {
                    break;
                }
                else {
                    x = zielone[jaki[pole]][0] + 1; y = zielone[jaki[pole]][1];
                    pole = jaki[pole];
                }
            }
            if ((x == x2 || (x - 1 == x2 && x != a)) && y <= y2) {
                cout << "Yes" << endl;
            }
            else {
                cout << "No" << endl;
            }
        }
    }
    return 0;
}

Compilation message

trampoline.cpp: In function 'int main()':
trampoline.cpp:38:13: warning: unused variable 'x_s' [-Wunused-variable]
   38 |         int x_s = x;
      |             ^~~

Subtask #1
23.0 / 23.0

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

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2039 ms 12412 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2040 ms 12544 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 820 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 58 ms 1108 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 39 ms 1116 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 173 ms 1104 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 51 ms 1112 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 159 ms 1104 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2036 ms 12284 KB Time limit exceeded
2 Halted 0 ms 0 KB -