oj.uz

Submission #752088

# Submission time Handle Problem Language Result Execution time Memory
752088 2023-06-02T09:29:06 Z Stickfish Trampoline (info1cup20_trampoline) C++17
73 / 100
 2000 ms 25060 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 5460 KB 200 token(s): yes count is 21, no count is 179
2 Correct 10 ms 5400 KB 200 token(s): yes count is 70, no count is 130
3 Correct 8 ms 5280 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 153 ms 13616 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 156 ms 13504 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 149 ms 12980 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 167 ms 13620 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 749 ms 23964 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 737 ms 23860 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 754 ms 23672 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 785 ms 23928 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 832 ms 23952 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 869 ms 25060 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 26 ms 5532 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 25 ms 5532 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 30 ms 5556 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 24 ms 5464 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 32 ms 5396 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 24 ms 5544 KB 5000 token(s): yes count is 3390, no count is 1610

Subtask #5
0 / 27.0

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