oj.uz

Submission #845450

# Submission time Handle Problem Language Result Execution time Memory
845450 2023-09-06T13:39:17 Z M_W_13 Trampoline (info1cup20_trampoline) C++17
42 / 100
 2000 ms 16524 KB 
#include <iostream>
#include <vector>
#include <map>
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 t;
    cin >> t;
    if (n > 5000 && t > 5000 || n == 5) {
        map <int, int> mapa;
        for (int i = 0; i < n; i++) {
            if (mapa[zielone[i][0]]) {
                if (mapa[zielone[i][0]] > zielone[i][1]) {
                    mapa[zielone[i][0]] = zielone[i][1];
                }
            }
            else {
                mapa[zielone[i][0]] = zielone[i][1];
            }
        }
        for (int i = 0; i < t; i++) {
            int x, y, x2, y2;
            cin >> x >> y >> x2 >> y2;
            if (mapa[x]) {
                if (mapa[x] <= y2 && mapa[x] >= y) {
                    cout << "Yes" << endl;
                }
                else {
                    cout << "No" << endl;
                }
            }
            else {
                cout << "No" << endl;
            }
        }
    }
    else {
        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;
                        }
                    }
                }
            }
        }
        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:20:18: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   20 |     if (n > 5000 && t > 5000 || n == 5) {
      |         ~~~~~~~~~^~~~~~~~~~~
trampoline.cpp:68:17: warning: unused variable 'x_s' [-Wunused-variable]
   68 |             int x_s = x;
      |                 ^~~

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 916 KB 200 token(s): yes count is 21, no count is 179
2 Correct 82 ms 920 KB 200 token(s): yes count is 70, no count is 130
3 Correct 41 ms 856 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 2021 ms 13308 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

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

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 1060 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 54 ms 816 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 49 ms 604 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 180 ms 600 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 50 ms 604 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 151 ms 808 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
0 / 27.0

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