Submission #769785

#	Time	Username	Problem	Language	Result	Execution time	Memory
769785		borisAngelov	Trampoline (info1cup20_trampoline)	C++17	0 / 100	2061 ms	2072 KiB

trampoline

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

const int maxn = 200005;

int r, c, n;

pair<int, int> a[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> r >> c >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].first >> a[i].second;
    }

    sort(a + 1, a + n + 1);

    int q;
    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;

        if (x1 > x2 || y1 > y2)
        {
            cout << "No\n";
            continue;
        }

        if (x1 == x2)
        {
            cout << "Yes\n";
            continue;
        }

        int l = 1;
        int r = n;

        while (l <= r)
        {
            int mid = (l + r) / 2;

            if (a[mid] >= make_pair(x1, y1))
            {
                r = mid - 1;
            }
            else
            {
                l = mid + 1;
            }
        }

        if (l == n + 1)
        {
            cout << "No\n";
            continue;
        }

        if (a[l].first != x1)
        {
            cout << "No\n";
            continue;
        }

        pair<int, int> curr = a[l];
        ++curr.first;

        for (int j = l + 1; j <= n; ++j)
        {
            if (a[j].first > curr.first)
            {
                cout << "No\n";
                break;
            }

            if (a[j].first == curr.first)
            {
                if (a[j].second > curr.second)
                {
                    curr = a[j];
                    ++curr.first;

                    if (curr.first == x2)
                    {
                        if (curr.second > y2)
                        {
                            cout << "No\n";
                            break;
                        }

                        cout << "Yes\n";
                        break;
                    }
                    else if (curr.second > y2)
                    {
                        cout << "No\n";
                        break;
                    }
                }
            }
        }
    }

    return 0;
}
/*
4 5 2
2 2
3 4
1
2 1 4 5
*/

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