Submission #1177869

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177869		LmaoLmao	Trampoline (info1cup20_trampoline)	C++20	11 / 100	316 ms	79604 KiB

trampoline

#include<bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<ll, ll>;
using aa = array<int,3>;

const int N = 1e6+1;
const int INF = 1e9;

vector<int> nen;
vector<aa> green;
vector<ii> mp[200005];
bool ans[200005];
ii up[200005][20];

int lift(int u,int y) {
    //cout << y << endl;
    int res=0;
    for(int i=19;i>=0;i--) {
        if(y>=(1<<i)) {
            y-=(1<<i);
            res=up[u][i].se;
            u=up[u][i].fi;
        }
    }
    if(u==0) return 1e9;
    else return res;
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n;
    cin >> n >> n >> n;
    for(int i=1;i<=n;i++) {
        int x,y;
        cin >> x >> y;
        nen.push_back(x);
        green.push_back({x,y,i});
    }
    sort(nen.begin(),nen.end());
    nen.resize(unique(nen.begin(),nen.end())-nen.begin());
    sort(green.begin(),green.end());
    for(int i=0;i<green.size();i++) {
        int x=lower_bound(nen.begin(),nen.end(),green[i][0])-nen.begin();
        mp[x].push_back({green[i][1],i+1});
    }
    for(int i=0;i<nen.size();i++) {
        sort(mp[i].begin(),mp[i].end());
    }
    for(int i=0;i<nen.size()-1;i++) {
        int j=0;
        if(nen[i]+1!=nen[i+1]) continue;
        for(ii x:mp[i]) {
            if(j<mp[i+1].size() && mp[i+1][j].fi<x.fi) {
                j++;
            }
            if(j!=mp[i+1].size()) {
                up[x.se][0]={mp[i+1][j].se,mp[i+1][j].fi};
            }
        }
    }
    for(int j=1;j<20;j++) {
        for(int i=1;i<=n;i++) {
            up[i][j]=up[up[i][j-1].fi][j-1];
        }
    }
    int q;
    cin >> q;
    for(int i=1;i<=q;i++) {
        int x1,y1,x2,y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if(x1>x2) {
            cout << "No" << '\n';
            continue;
        }
        if(x1==x2) {
            if(y2>=y1) cout << "Yes";
            else cout << "No";
            cout << '\n';
            continue;
        }
        if(x2-x1>n) {
            cout << "No" << '\n';
            continue;
        }
        int x=lower_bound(nen.begin(),nen.end(),x1)-nen.begin();
        if(x1!=nen[x]) {
            cout << "No" << '\n';
            continue;
        }
        int y=lower_bound(mp[x].begin(),mp[x].end(),make_pair(y1,0LL))-mp[x].begin();
        if(y==mp[x].size()) {
            cout << "No" << '\n';
            continue;
        }
        if(x2-x1-1==0) {
          if(mp[x][y].fi<=y2) cout << "Yes";
          else cout << "No";
          cout << endl;
          continue;
        }
        if(lift(mp[x][y].se,x2-x1-1)<=y2) {
              cout << "Yes";
        } else cout << "No";
        cout << '\n';
    }
    return 0;
}

/*
██╗░░██╗██╗░░██╗░█████╗░███╗░░██╗░██████╗░              ░██████╗██╗██╗░░░██╗                ░█████╗░██╗░░░██╗████████╗███████╗
██║░██╔╝██║░░██║██╔══██╗████╗░██║██╔════╝░              ██╔════╝██║██║░░░██║                ██╔══██╗██║░░░██║╚══██╔══╝██╔════╝
█████═╝░███████║███████║██╔██╗██║██║░░██╗░              ╚█████╗░██║██║░░░██║                ██║░░╚═╝██║░░░██║░░░██║░░░█████╗░░
██╔═██╗░██╔══██║██╔══██║██║╚████║██║░░╚██╗              ░╚═══██╗██║██║░░░██║                ██║░░██╗██║░░░██║░░░██║░░░██╔══╝░░
██║░╚██╗██║░░██║██║░░██║██║░╚███║╚██████╔╝              ██████╔╝██║╚██████╔╝                ╚█████╔╝╚██████╔╝░░░██║░░░███████╗
╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚═╝╚═╝░░╚══╝░╚═════╝░              ╚═════╝░╚═╝░╚═════╝░                ░╚════╝░░╚═════╝░░░░╚═╝░░░╚══════╝
*/

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