Submission #921199

#	Time	Username	Problem	Language	Result	Execution time	Memory
921199		WongYiKai	Trampoline (info1cup20_trampoline)	C++14	11 / 100	856 ms	113740 KiB

trampoline

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

/* Pre-computation using DFS */
const int MAXN = 600000;
const int LOGN = 20;
int p[LOGN+1][MAXN],h[MAXN];
vector<int> adjList[MAXN];
bitset<MAXN> visited;
void dfs(int x) {
    // cout << x << " ";
    if (visited[x]) return;
    visited[x] = 1;
    for (int k = 0; k < LOGN; ++k) {
        if (p[k][x] == -1) break;
        p[k+1][x] = p[k][p[k][x]];
    }
    for (auto it:adjList[x]) {
        if (visited[it]) continue;
        p[0][it] = x;
        h[it] = h[x]+1;
        dfs(it);
    }
}

/* Per query, d-th ancestor of x */
int ancestor(int x, int d) {
    for (int k = 0; k <= LOGN && x != -1; ++k) {
        if (d & (1<<k)) 
            x = p[k][x];
    }
    return x;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll r,c,n;
    cin >> r >> c >> n;
    priority_queue<pair<ll,ll>,vector<pair<ll,ll>>,greater<pair<ll,ll>>> pq;
    vector<pair<ll,ll>> mem;
    map<ll,set<ll>> m;
    map<ll,ll> far;
    for (int i=0;i<n;i++){
        ll a,b;
        cin >> a >> b;
        pq.push({a,b});
        m[a].insert(b);
        far[a] = max(far[a],b);
    }
    queue<ll> q;
    ll prev=0;
    ll count=-1;
    map<pair<ll,ll>,ll> mem2;
    while (!pq.empty()){
        ll a=pq.top().first;
        ll b=pq.top().second;
        if (a!=prev){
            if (a!=prev+1){
                while (!q.empty()){
                    // cout << "a" << " ";
                    dfs(q.front());
                    q.pop();
                }
            }
            else {
                while (!q.empty() && mem[q.front()].first!=prev){
                    // cout << "b" << " ";
                    dfs(q.front());
                    q.pop();
                }
            }
        }
        mem.push_back({a,b});
        count++;
        mem2[{a,b}] = count;
        while (!q.empty() && mem[q.front()].second <= b){
            adjList[count].push_back(q.front());
            adjList[q.front()].push_back(count);
            q.pop();
        }
        q.push(count);
        prev=a;
        pq.pop();
    }
    while (!q.empty()){
        // cout << "c" << " ";
        dfs(q.front());
        q.pop();
    }
    // for (int i=0;i<n;i++) cout << h[i] << " ";
    ll t;
    cin >> t;
    for (int i=0;i<t;i++){
        ll x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1>x2) {
            cout << "No" << "\n";
            continue;
        }
        if (y2<y1){
            cout << "No" << "\n";
            continue;
        }
        if (x1==x2) {
            cout << "Yes" << "\n";
            continue;
        }
        auto vertex = m[x1].lower_bound(y1);
        if (y1 > far[x1]){
            cout << "No" << "\n";
            continue;
        }
        ll ind = mem2[{x1,*vertex}];
        ll dist = x2-x1-1;
        if (h[ind]<dist){
            cout << "No" << "\n";
            continue;
        }
        ll temp = ancestor(ind,dist);
        ll end = mem[temp].second;
        if (end <= y2) cout << "Yes" << "\n";
        else cout << "No" << "\n";
    }
// cout << ancestor(0,0);
}

• Subtask 1: 0 / 23
• Subtask 2: 0 / 20
• Subtask 3: 11 / 11
• Subtask 4: 0 / 19
• Subtask 5: 0 / 27