Submission #769801

#	Time	Username	Problem	Language	Result	Execution time	Memory
769801		borisAngelov	Trampoline (info1cup20_trampoline)	C++17	100 / 100	333 ms	29224 KiB

trampoline

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

using namespace std;

const int maxn = 200005;
const int max_log = 20;

int r, c, n;

pair<int, int> a[maxn];

int sorted_indexes[maxn];

int sparse[max_log][maxn];

int lifting(int start, int times)
{
    if (times >= n + 1)
    {
        return 0;
    }

    int res = start;

    for (int log = max_log - 1; log >= 0; --log)
    {
        if ((times & (1 << log)) == 0)
        {
            continue;
        }

        res = sparse[log][res];
    }

    return res;
}

int binary(int x, int y)
{
    int l = 1;
    int r = n;

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

        if (a[sorted_indexes[mid]].first != x)
        {
            if (a[sorted_indexes[mid]].first < x)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
        else
        {
            if (a[sorted_indexes[mid]].second < y)
            {
                l = mid + 1;
            }
            else
            {
                r = mid - 1;
            }
        }
    }

    if (a[sorted_indexes[l]].first == x && a[sorted_indexes[l]].second >= y)
    {
        return sorted_indexes[l];
    }

    return 0;
}

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)
    {
        sorted_indexes[i] = i;
        cin >> a[i].first >> a[i].second;
    }

    sort(sorted_indexes + 1, sorted_indexes + n + 1, [&](int x, int y)
    {
        return a[x] <= a[y];
    });

    int ptr = 1;

    for (int i = 1; i <= n; ++i)
    {
        int l_idx = sorted_indexes[i];
        int r_idx = sorted_indexes[ptr];

        while (ptr <= n && (a[r_idx].first == a[l_idx].first || (a[r_idx].first == a[l_idx].first + 1 && a[r_idx].second < a[l_idx].second)))
        {
            ++ptr;
            r_idx = sorted_indexes[ptr];
        }

        if (ptr <= n && a[r_idx].first == a[l_idx].first + 1 && a[r_idx].second >= a[l_idx].second)
        {
            sparse[0][l_idx] = r_idx;
        }
        else
        {
            sparse[0][l_idx] = 0;
        }
    }

    for (int log = 1; (1 << log) <= n; ++log)
    {
        for (int i = 1; i <= n; ++i)
        {
            sparse[log][i] = sparse[log - 1][sparse[log - 1][i]];
        }
    }

    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 curr = binary(x1, y1);

        int res = lifting(curr, x2 - x1 - 1);

        if (curr != 0 && res != 0 && a[res].second <= y2)
        {
            cout << "Yes\n";
        }
        else
        {
            cout << "No\n";
        }
    }

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

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