Submission #612223

#	Time	Username	Problem	Language	Result	Execution time	Memory
612223		boris_mihov	Trampoline (info1cup20_trampoline)	C++14	100 / 100	472 ms	29264 KiB

trampoline

#include <algorithm>
#include <iostream>
#include <numeric>
#include <set>

typedef long long llong;
const int MAXN = 200000 + 10;
const int MAXLOG = 20;

int perm[MAXN], r, c, n, q;
std::pair < int,int > g[MAXN];
int sparse[MAXLOG][MAXN];

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

    int num = start;
    for (int log = MAXLOG-1 ; log >= 0 ; --log)
    {
        if (!(times & (1 << log))) continue;
        num = sparse[log][num];
    }

    return num;
}

int binSearch(int x, int y)
{
    int l = 0, r = n+1, mid;
    while (l < r - 1)
    {
        mid = (l + r) / 2;
        if (g[perm[mid]].first != x)
        {
            if (g[perm[mid]].first < x) l = mid;
            else r = mid;
        } else
        {
            if (g[perm[mid]].second < y) l = mid;
            else r = mid;
        }
    }

    if (g[perm[r]].first == x && g[perm[r]].second >= y) return perm[r];
    return 0;
}

void solve()
{
    std::iota(perm+1, perm+1+n, 1);
    std::sort(perm+1, perm+1+n, [&](int x, int y)
    {
        return g[x] < g[y];
    });

    int rp = 1;
    for (int lp = 1 ; lp <= n ; ++lp)
    {
        int rIdx = perm[rp];
        int lIdx = perm[lp];
        while (rp <= n && (g[rIdx].first == g[lIdx].first || (g[rIdx].first == g[lIdx].first + 1 && g[rIdx].second < g[lIdx].second)))
        {
            rp++;
            rIdx = perm[rp];
        }

        if (rp <= n && g[rIdx].first == g[lIdx].first + 1 && g[rIdx].second >= g[lIdx].second) 
        {
            sparse[0][lIdx] = rIdx;
        } else sparse[0][lIdx] = 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 xs, ys, xe, ye;
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cin >> xs >> ys >> xe >> ye;
        if (xs >= xe+1 || ys >= ye+1)
        {
            std::cout << "No\n";
            continue;
        }

        if (xs == xe)
        {
            std::cout << "Yes\n";
            continue;
        }

        int curr = binSearch(xs, ys);
        int res = lifting(curr, xe - xs - 1);
        if (curr != 0 && res != 0 && g[res].second <= ye) std::cout << "Yes\n";
        else std::cout << "No\n";
    }
}

void read()
{
    std::cin >> r >> c >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> g[i].first >> g[i].second;
    }

    std::cin >> q;
}

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

int main()
{
    fastIO();
    read();
    solve();
    
    return 0;
}

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