oj.uz

Submission #769785

# Submission time Handle Problem Language Result Execution time Memory
769785 2023-06-30T09:09:58 Z borisAngelov Trampoline (info1cup20_trampoline) C++17
0 / 100
 2000 ms 2072 KB 
#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.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 340 KB expected YES, found NO [3rd token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

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