oj.uz

Submission #612223

# Submission time Handle Problem Language Result Execution time Memory
612223 2022-07-29T11:43:27 Z boris_mihov Trampoline (info1cup20_trampoline) C++14
100 / 100
 472 ms 29264 KB 
#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.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 980 KB 200 token(s): yes count is 21, no count is 179
2 Correct 4 ms 1048 KB 200 token(s): yes count is 70, no count is 130
3 Correct 3 ms 876 KB 197 token(s): yes count is 25, no count is 172

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 16720 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 68 ms 18600 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 70 ms 18216 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 69 ms 18604 KB 4000 token(s): yes count is 1991, no count is 2009

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 265 ms 17472 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 224 ms 29080 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 295 ms 29084 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 234 ms 29260 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 260 ms 29136 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 218 ms 29004 KB 200000 token(s): yes count is 97163, no count is 102837

Subtask #4
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 724 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 5 ms 980 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 6 ms 980 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 5 ms 1036 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 5 ms 976 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 5 ms 988 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 17456 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 368 ms 29152 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 227 ms 29136 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 419 ms 29068 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 273 ms 29120 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 274 ms 29136 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 242 ms 29188 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 228 ms 29184 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 360 ms 29124 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 352 ms 29152 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 472 ms 29116 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 214 ms 29148 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 243 ms 29264 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 291 ms 29244 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 211 ms 29244 KB 200000 token(s): yes count is 129674, no count is 70326