Submission #1317120

#TimeUsernameProblemLanguageResultExecution timeMemory
1317120hssaan_arifTrampoline (info1cup20_trampoline)C++20
0 / 100
125 ms35496 KiB
// #include <bits/stdc++.h> #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <unordered_map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> using namespace std; #define endl "\n" #define pb push_back #define int long long #define fi first #define se second #define pii pair<int,int> const int N = 3e5 + 5, M = 1e9 + 7, LG = 20; int n , r , c , sp[N][LG] , q , x , y , a , b; pii A[N]; void solve(){ cin >> r >> c >> n; for (int i=0 ; i<n ; i++){ cin >> A[i].fi >> A[i].se; } int j=1; for (int i=0 ; 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){ sp[i][0] = j; }else{ sp[i][0] = n; } } sp[n][0] = n; for (int j=1 ; j<LG ; j++){ for (int i=0 ; i<n ; i++){ sp[i][j] = sp[sp[i][j-1]][j-1]; } } cin >> q; while(q--){ cin >> x >> y >> a >> b; if (a < x || b < y){ cout << "NO" << endl; continue; } if (a==x){ cout << "YES" << endl; continue; } int nx = lower_bound(A,A+n,pii(x,y)) - A; if (A[nx].fi != x){ cout << "NO" << endl; continue; } for (int i=LG-1 ; i>=0 ; i--){ if (x + (1<<i) < a){ x += (1<<i); nx = sp[nx][i]; } } if (nx == n){ cout << "NO" << endl; continue; } if (A[nx].se <= b){ cout << "YES" << endl; }else{ cout << "NO" << endl; } } } signed main(){ // freopen("" , "r" , stdin); // freopen("" , "w" , stdout); // cout << setprecision(30); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int ts = 1; // cin >> ts; while(ts--){ solve(); } }
#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...