# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1027579 | vjudge1 | Trampoline (info1cup20_trampoline) | C++17 | 2048 ms | 48332 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
void f(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
#endif
}
signed main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
//f();
int n, m, t; cin >> n >> m >> t;
vector<array<int, 2>> tram(t);
vector<array<int, 20>> p(t+1);
for(auto &[i, l]: tram) cin >> i >> l;
sort(tram.begin(), tram.end());
vector<array<int, 2>> ol;
int pos=-1;
for(int i=t-1; i>=0; i--){
auto [r, c]=tram[i];
if(i<t-1&&tram[i+1][0]!=r){
ol.clear();
for(int j=i+1; j<t; j++){
if(tram[j][0]==r+1){
ol.push_back({tram[j][1], j});
}
}
pos=ol.size()-1;
}
while(pos>=0&&ol[pos-1][0]>=c) pos--;
if(pos<0){
p[i][0]=i;
}
else{
p[i][0]=ol[pos][1];
}
}
for(int l=1; l<20; l++){
for(int i=0; i<t; i++){
p[i][l]=p[p[i][l-1]][l-1];
}
}
int q; cin >> q;
while(q--){
int x, y; cin >> x >> y;
int pos=lower_bound(tram.begin(), tram.end(), (array<int, 2>){x, y})-tram.begin();
int ex, ey; cin >> ex >> ey;
if(ex==x){
if(y<=ey) cout<<"Yes";
else cout<<"No";
}
else if(ex<x){
cout<<"No";
}
else if(tram.size()==pos) cout<<"No";
else if(tram[pos][0]!=x) cout<<"No";
else{
int dif=ex-x-1;
for(int j=19; j>=0; j--){
if((1<<j)<=dif){
pos=p[pos][j];
dif-=(1<<j);
}
}
if(tram[pos][0]==ex-1&&tram[pos][1]<=ey){
cout<<"Yes";
}
else cout<<"No";
}
cout<<"\n";
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |