Submission #845428

#	Time	Username	Problem	Language	Result	Execution time	Memory
845428		M_W_13	Trampoline (info1cup20_trampoline)	C++17	42 / 100	2049 ms	16252 KiB

trampoline

#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) {
        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) {
                    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 (stderr)

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

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