oj.uz

Submission #1059303

# Submission time Handle Problem Language Result Execution time Memory
1059303 2024-08-14T20:44:21 Z jnjwnwnw Trampoline (info1cup20_trampoline) C++17
100 / 100
 1008 ms 81492 KB 
#include <iostream>
#include <algorithm>    
#include <map>
#include <vector>
#include <set>
using namespace std;

#define ll long long
#define fff(i,a,b) for (int i = a; i < b; i++)
#define fffm(i,a,b) for (int i = a; i > b; i--)

#define MAXN 200005
map<ll, set<pair<ll, ll>>> xs;
ll parent[MAXN][22], Y[MAXN], X[MAXN];
ll R, C, n, T;

// class comp{
//     public:
//     bool operator()(const pair<ll, ll>& a, const pair<ll, ll>& b) const{
//         if (a.first == b.first) return a.second < b.second;
//         return a.first < b.first;
//     }
// };

int main(){
    cin >> R >> C >> n;
    fff(i, 0, n){
        cin >> Y[i] >> X[i];
        xs[Y[i]].insert({X[i], i});
    }

    // for(auto& [a, b]: xs){
    //     sort(b.begin(), b.end());
    // }

    fff(i, 0, n){
        // cout << "A" << endl;
        ll y = Y[i], x = X[i];
        parent[i][0] = i;
        if (xs[y-1].size() == 0) continue;
        // cout << "B" << endl;
        auto ptr = xs[y-1].upper_bound({x, INT32_MAX});
        // if (ptr == xs[y-1].end()) ptr--;
        if (ptr == xs[y-1].begin()) continue;
        ptr--;
        // cout << "C" << endl;
        auto [x2, ind] = *ptr;
        if (x2 > x) continue;
        // cout << "D" << endl;
        // this is fine, so parent here
        parent[i][0] = ind;
        // cout << i << " " << y << " " << x << " " << parent[i][0] << endl;
        // cout << i  << " " << parent[i][0] << endl;
    }

    // now, do LCA stuff
    fff(i, 1, 22){
        fff(j, 0, n){
            parent[j][i] = parent[parent[j][i-1]][i-1];
        }
    }
    cin >> T;
    fff(i, 0, T){
        ll y1, x1, y2, x2; cin >> y1 >> x1 >> y2 >> x2;
        if (y2 < y1 || x2 < x1){
            cout << "NO" << endl;
            continue;
        }
        if (y2 == y1){
            cout << "YES" << endl;
            continue;
        }
        if (xs[y2-1].size() == 0){
            cout << "NO" << endl;
            continue;
        }
        auto ptr = xs[y2-1].upper_bound({x2, INT64_MAX});

        if (ptr == xs[y2-1].begin()){
            cout << "NO" << endl;
            continue;
        }
        ptr--;
        // cout << "YAY" << endl;
        ll ind = ptr->second;
        // cout << ind << " " << parent[ind][0] << endl;
        fffm(amt, 21, -1){
            if (Y[parent[ind][amt]] >= y1){
                ind = parent[ind][amt];
                // cout << "AAA " << ind << endl;
            }
        }
        // ind is now at the right level hopefully
        if (Y[ind] != y1 || X[ind] < x1){
            cout << "NO" << endl;
            continue;
        }
        cout << "YES" << endl;

    }
}

Subtask #1
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2652 KB 200 token(s): yes count is 21, no count is 179
2 Correct 6 ms 2908 KB 200 token(s): yes count is 70, no count is 130
3 Correct 5 ms 2140 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 209 ms 52444 KB 4000 token(s): yes count is 99, no count is 3901
2 Correct 224 ms 52564 KB 4000 token(s): yes count is 91, no count is 3909
3 Correct 206 ms 52024 KB 4000 token(s): yes count is 4000, no count is 0
4 Correct 218 ms 52560 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 663 ms 62800 KB 200000 token(s): yes count is 110486, no count is 89514
2 Correct 673 ms 62828 KB 200000 token(s): yes count is 114664, no count is 85336
3 Correct 824 ms 62788 KB 200000 token(s): yes count is 86232, no count is 113768
4 Correct 738 ms 63052 KB 200000 token(s): yes count is 94603, no count is 105397
5 Correct 773 ms 63060 KB 200000 token(s): yes count is 94148, no count is 105852
6 Correct 805 ms 69012 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 16 ms 2024 KB 5000 token(s): yes count is 3238, no count is 1762
2 Correct 15 ms 1884 KB 5000 token(s): yes count is 3837, no count is 1163
3 Correct 15 ms 2908 KB 5000 token(s): yes count is 4104, no count is 896
4 Correct 13 ms 2020 KB 5000 token(s): yes count is 3934, no count is 1066
5 Correct 14 ms 2140 KB 5000 token(s): yes count is 3384, no count is 1616
6 Correct 14 ms 2020 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 807 ms 70228 KB 200000 token(s): yes count is 171404, no count is 28596
2 Correct 758 ms 64624 KB 200000 token(s): yes count is 161254, no count is 38746
3 Correct 701 ms 62768 KB 200000 token(s): yes count is 117455, no count is 82545
4 Correct 1008 ms 81492 KB 200000 token(s): yes count is 182118, no count is 17882
5 Correct 897 ms 69684 KB 200000 token(s): yes count is 167565, no count is 32435
6 Correct 661 ms 62900 KB 200000 token(s): yes count is 156797, no count is 43203
7 Correct 673 ms 62804 KB 200000 token(s): yes count is 156797, no count is 43203
8 Correct 729 ms 62816 KB 200000 token(s): yes count is 122100, no count is 77900
9 Correct 861 ms 69128 KB 200000 token(s): yes count is 139670, no count is 60330
10 Correct 892 ms 68948 KB 200000 token(s): yes count is 165806, no count is 34194
11 Correct 921 ms 75380 KB 200000 token(s): yes count is 175646, no count is 24354
12 Correct 596 ms 62804 KB 200000 token(s): yes count is 134695, no count is 65305
13 Correct 589 ms 62784 KB 200000 token(s): yes count is 126733, no count is 73267
14 Correct 704 ms 63064 KB 200000 token(s): yes count is 155290, no count is 44710
15 Correct 643 ms 62804 KB 200000 token(s): yes count is 129674, no count is 70326