Submission #524072

#	Time	Username	Problem	Language	Result	Execution time	Memory
524072		omohamadooo	Trampoline (info1cup20_trampoline)	C++14	0 / 100	841 ms	92824 KiB

trampoline

#include<bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ll long long
#define pb push_back
#define endl '\n'
#define pii pair<ll,ll >
#define F first
#define S second
#define double long double
#define all(x) (x).begin(),(x).end()
using namespace std;
using namespace __gnu_pbds;

typedef tree<ll , null_type , less_equal<ll> ,rb_tree_tag ,tree_order_statistics_node_update >ordered_set;

const int MOD=998244353 ;
const int  N=1e6+ 7;
const ll INF= 1e18+10;

struct trp{ll F,S,T;};

ll po(ll x,ll y)
{
    ll ans = 1;
    while(y){
        if( y & 1 ) ans *=x;
        y /= 2;
        x *=x;
        x %= MOD;
        ans %= MOD;
    }
    return ans;
}

ll r,c,n;
ll dep[N];
ll up[N][20];
map<ll,pii>inf;
vector<ll>v[N];
map<ll,vector<pii> >mp;

void dfs(ll x,ll p)
{
    up[x][0] = p;
    for(ll i=1;i<20;i++) up[x][i] = up[up[x][i-1]][i-1];
    for(auto i : v[x]){
        dep[i] = dep[x] + 1;
        assert(inf[i].F == inf[x].F+1 );
        assert(inf[i].S >= inf[x].S);
        dfs(i , x);
    }
}

ll get(ll node ,ll k)
{
    for(ll i=19;i>=0;i--){
        if((1LL << i) <= k){
            node = up[node][i];
            k -= (1LL << i);
        }
    }
    return node;
}

bool cmp(pii x,pii y)
{
    if(x.F != y.F) return x.F < y.F;
    assert(0);
}

void solve()
{
    cin >> r >> c >> n;
    for(ll i=1;i<=n;i++){
        ll x,y;
        cin >> x >> y;
        mp[x].pb({y,i});
        inf[i] = {x, y};
    }
    vector<ll>roots;
    for(auto i : mp) sort(all(i.S),cmp);
    for(auto i : mp){
        for(auto j : i.S){
            if(!mp[i.F-1].size() || mp[i.F-1][0].F > j.F){
                roots.pb(j.S);
            }
            else{
                ll l = 0 , r = mp[i.F-1].size()-1, mid;
                while(l < r){
                    mid = (l + r + 1)/2;
                    if(mp[i.F-1][mid].F <= j.F) l = mid;
                    else r = mid-1;
                }
                v[mp[i.F-1][l].S].pb(j.S);
            }
        }
    }
    for(auto i : roots){
        dep[i] = 1;
        dfs(i,i);
    }
    ll q;
    cin >> q;
    while(q -- ){
        ll x,y,z,w;
        cin >> x >> y >> z >> w;
        if(x > z ){
            cout << "No"<<endl;
            continue;
        }
        if(x == z){
            cout << (y <= w ? "Yes" : "No") << endl;
            continue;
        }
        if(!mp[z-1].size() || mp[z-1][0].F > w){
            cout << "No" << endl;
            continue;
        }

        ll l = 0 , r = mp[z-1].size()-1, mid;
        while(l < r){
            mid = (l + r + 1)/2;
            if(mp[z-1][mid].F <= w) l = mid;
            else r = mid-1;
        }
        ll node = mp[z-1][l].S;
        node = get(node , z-x);
        if(inf[node].F != x){
            cout << "No" << endl;
            continue;
        }
        cout << (inf[node].S >= y ? "Yes" : "No") << endl;
    }
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	//freopen("dishes.in" , "r" , stdin);freopen("dishes.out" , "w" , stdout);
	int t = 1;
    //cin >> t;
	while(t--) {solve() ; }
}

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