oj.uz

Submission #752090

# Submission time Handle Problem Language Result Execution time Memory
752090 2023-06-02T09:29:44 Z Stickfish Trampoline (info1cup20_trampoline) C++17
100 / 100
 958 ms 29128 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <bitset>
using namespace std;

const int MAXN = 2e5 + 123;
pair<int, int> pts[MAXN];
vector<int> ptr[MAXN];
int rt[MAXN];
int crt[MAXN];
int depth[MAXN];

int fup(int v, int x1) {
    if (pts[v].first >= x1 || rt[v] == v)
        return v;
    if (pts[crt[v]].first <= x1)
        return fup(crt[v], x1);
    return fup(rt[v], x1);
}

signed main() {
    int r, c, n;
    cin >> r >> c >> n;
    vector<int> cprx;
    for (int i = 0; i < n; ++i) {
        cin >> pts[i].first >> pts[i].second;
        cprx.push_back(pts[i].first);
        cprx.push_back(pts[i].first + 1);
    }
    sort(cprx.begin(), cprx.end());
    cprx.resize(unique(cprx.begin(), cprx.end()) - cprx.begin());
    int csz = cprx.size();
    sort(pts, pts + n);
    for (int i = 0; i < n; ++i) {
        int x = lower_bound(cprx.begin(), cprx.end(), pts[i].first) - cprx.begin();
        pts[i].first = x;
        ptr[x].push_back(pts[i].second);
    }
    for (int i = 0; i < n; ++i) {
        int x = pts[i].first;
        int j = lower_bound(pts, pts + n, pair<int, int>(x + 1, pts[i].second)) - pts;
        if (j == n || pts[j].first != x + 1) {
            rt[i] = i;
        } else {
            rt[i] = j;
        }
    }
    //for (int i = 0; i < n; ++i) {
        //cout << i << ": (" << cprx[pts[i].first] << ' ' << ' ' << pts[i].second << ") : " << rt[i] << "\n";
    //}
    for (int v = n - 1; v >= 0; --v) {
        crt[v] = rt[v];
        if (rt[v] == v)
            continue;
        depth[v] = depth[rt[v]] + 1;
        if (depth[rt[v]] + depth[crt[crt[rt[v]]]] == 2 * depth[crt[rt[v]]])
            crt[v] = crt[crt[rt[v]]];
    }
    int T;
    cin >> T;
    for (int t = 0; t < T; ++t) {
        pair<int, int> p0, p1;
        cin >> p0.first >> p0.second >> p1.first >> p1.second;
        if (p0.first > p1.first || p0.second > p1.second) {
            cout << "No\n";
            continue;
        }
        if (p0.first == p1.first) {
            cout << "Yes\n";
            continue;
        }
        int x0 = lower_bound(cprx.begin(), cprx.end(), p0.first) - cprx.begin();
        int x1 = lower_bound(cprx.begin(), cprx.end(), p1.first) - cprx.begin();
        if (x1 == csz || p0.first != cprx[x0] || p1.first != cprx[x1]) {
            cout << "No\n";
            continue;
        }
        p0.first = x0;
        p1.first = x1;
        int v = lower_bound(pts, pts + n, p0) - pts;
        //cout << "HAHA " << v << endl;
        if (pts[v].first != x0) {
            cout << "No\n";
            continue;
        }
        int u = fup(v, x1 - 1);
        if (pts[u].first != x1 - 1  || pts[u].second > p1.second) {
            cout << "No\n";
            continue;
        }
        cout << "Yes\n";
    }
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 5332 KB 200 token(s): yes count is 21, no count is 179
2 Correct 9 ms 5332 KB 200 token(s): yes count is 70, no count is 130
3 Correct 8 ms 5204 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 160 ms 11644 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 164 ms 11740 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 138 ms 11456 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 152 ms 11756 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 772 ms 12392 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 803 ms 12212 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 783 ms 12116 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 842 ms 12408 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 796 ms 12252 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 828 ms 13344 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 22 ms 5204 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 24 ms 5236 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 22 ms 5288 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 22 ms 5204 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 22 ms 5240 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 22 ms 5180 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 957 ms 20472 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 958 ms 24404 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 778 ms 23812 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 940 ms 29128 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 815 ms 26012 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 862 ms 23864 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 858 ms 23820 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 748 ms 23736 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 934 ms 25172 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 949 ms 25128 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 950 ms 26964 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 738 ms 24324 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 807 ms 24008 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 854 ms 23976 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 766 ms 24052 KB 200000 token(s): yes count is 129674, no count is 70326