제출 #1317044

#제출 시각아이디문제언어결과실행 시간메모리
1317044AMnuTrampoline (info1cup20_trampoline)C++20
100 / 100
212 ms16844 KiB
#include <bits/stdc++.h> #define fi first #define se second using namespace std; typedef long long ll; typedef pair<int,int> pii; const int MAXN = 2e5+5, LOG = 18; const ll INF = 1e18; int X, Y, N, T, Xf, Yf, P[MAXN][LOG]; pii A[MAXN]; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> X >> Y >> N; for (int i=0;i<N;i++) { cin >> A[i].fi >> A[i].se; } sort(A,A+N); for (int i=0,j=1;i<N;i++) { while (j < N && A[j] < pii(A[i].fi+1,A[i].se)) { j++; } if (A[j].fi == A[i].fi+1) { P[i][0] = j; } else { P[i][0] = N; } } P[N][0] = N; for (int i=1;i<LOG;i++) { for (int j=0;j<=N;j++) { P[j][i] = P[P[j][i-1]][i-1]; } } cin >> T; while (T--) { cin >> X >> Y >> Xf >> Yf; if (Xf < X || Yf < Y) { cout << "No\n"; continue; } if (Xf == X) { cout << "Yes\n"; continue; } int now = lower_bound(A,A+N,pii(X,Y))-A; if (A[now].fi != X) { cout << "No\n"; continue; } for (int i=LOG-1;i>=0;i--) { if (X+(1<<i) < Xf) { X += 1<<i; now = P[now][i]; } } if (now == N) { cout << "No\n"; continue; } if (Yf >= A[now].se) { cout << "Yes\n"; } else { cout << "No\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...