oj.uz

Submission #1059275

# Submission time Handle Problem Language Result Execution time Memory
1059275 2024-08-14T20:16:00 Z jnjwnwnw Trampoline (info1cup20_trampoline) C++17
0 / 100
 846 ms 70156 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 << endl;
        fffm(amt, 22, -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
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 6 ms 2652 KB expected YES, found NO [5th token]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 247 ms 52560 KB expected YES, found NO [12th token]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 659 ms 62784 KB expected YES, found NO [9th token]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 14 ms 1884 KB expected YES, found NO [1st token]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 846 ms 70156 KB expected YES, found NO [5th token]
2 Halted 0 ms 0 KB -