Submission #1136357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136357		bpptidp	Trampoline (info1cup20_trampoline)	C++20	100 / 100	771 ms	68568 KiB

trampoline

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

const int mod=1e9+7,T=69420;
struct ah{size_t operator()(const array<int,2>&a)const{return (int)((ll)a[0]*T+(ll)a[1])%mod;}};

int R,C,n,t;
unordered_map<int,set<int>>rw;
unordered_map<array<int,2>,int,ah>hsh;
vector<array<int,2>>zel;
set<array<int,2>>ss;

const int N=(1<<18)+22;
array<int,2>dehsh[N];
int go[N][19];

signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin>>R>>C>>n;
    for(int i=0;i<n;++i){
    	int x,y;
    	cin>>x>>y;
    	rw[x].insert(y);
    	ss.insert({x,y});
    	zel.push_back({x,y});
    }

    int cc=0;
    for(auto&x:ss){
    	hsh[x]=++cc;
    	dehsh[cc]=x;
    }

   	for(auto&[x,s]:rw){
   		for(auto&y:s){
   			auto it=rw[x+1].lower_bound(y);
   			if(it==rw[x+1].end())continue;
   			go[hsh[{x,y}]][0]=hsh[{x+1,*it}];
   		}
   	}

   	for(int j=1;j<19;++j){
   		for(int i=0;i<n;++i){
   			int x=hsh[zel[i]];
   			go[x][j]=go[go[x][j-1]][j-1];
   		}
   	}

   	cin>>t;
   	while(t--){
   		int x1,y1,x2,y2;
   		cin>>x1>>y1>>x2>>y2;
   		if(x1>x2||y1>y2){cout<<"No\n";continue;};
   		if(x1==x2){cout<<"Yes\n";continue;}
   		int dst=x2-x1-1;
   		auto lik=rw[x1].lower_bound(y1);
   		if(lik==rw[x1].end()){cout<<"No\n";continue;};
   		int z=hsh[{x1,*lik}];
   		for(int j=18;~j;--j)
   			if(dst&(1<<j))z=go[z][j];
   		int y=dehsh[z][1];
   		cout<<(y<=y2&&z?"Yes\n":"No\n");
   	}
}

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