Submission #482032

#TimeUsernameProblemLanguageResultExecution timeMemory
482032RedhoodTrampoline (info1cup20_trampoline)C++14
100 / 100
592 ms76984 KiB
#include<bits/stdc++.h> #define pb push_back #define all(x) (x).begin(), (x).end() #define sz(x) (int)(x).size() #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define fi first #define se second using namespace __gnu_pbds; using namespace std; using namespace __gnu_cxx; using namespace std; const int N = (int)2e5 + 10; vector < int > g[N]; int pred[N], h[N]; int son[N], used[N]; array < int , 4 > q[N];/// x1 , y1 , x2 , y2 bool ans[N]; vector < int > stac; vector < pair < int , int > > dots; vector < int > que[N]; vector < int > P[N], y[N]; void dfs(int v, int H){ stac.pb(v); used[v] = 1; h[v] = H; for(auto &i : que[v]){ int w = q[i][2] - q[i][0] - 1; if(h[v] < w){ continue; } int id = sz(stac)-1-w; int par = stac[id]; if(dots[par].se <= q[i][3]){ ans[i] = 1; } } for(auto u : g[v]){ assert(!used[u]); pred[u] = v; dfs(u, H + 1); } stac.pop_back(); } int main() { ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0); int R , C, n , t; cin >> R >> C >> n; dots.resize(n); for(auto &i : dots) cin >> i.fi >> i.se; cin >> t; vector < int > rows; for(auto &i : dots) rows.pb(i.fi); sort(all(rows)); rows.erase(unique(all(rows)), rows.end()); reverse(all(rows)); vector < int > perm(n); iota(all(perm) , 0); sort(all(perm) , [&](int x , int y){ if(dots[x].fi == dots[y].fi){ return dots[x].se < dots[y].se; } return dots[x].fi > dots[y].fi; }); int lst = 0; vector < int > cand, val; int jj = 0; for(int r : rows){ vector < int > cur; while(lst < sz(perm) && dots[perm[lst]].fi == r){ /// add it y[jj].pb(dots[perm[lst]].se); P[jj].pb(perm[lst]); cur.pb(perm[lst]); int id = lower_bound(all(val) , dots[perm[lst]].se) - val.begin(); if(id != sz(val)){ int par = cand[id]; son[perm[lst]] = 1; g[par].pb(perm[lst]); } lst++; } cand.clear(), val.clear(); for(int f : cur){ cand.pb(f); val.pb(dots[f].se); } vector<int>t=val; sort(all(t)); assert(t==val); jj++; } reverse(all(rows)); /// reversed oder for(int i = 0 ; i < t; ++i){ int x1 , y1 , x2 , y2; cin >> x1 >> y1 >> x2 >> y2; if(x1 > x2 || y1 > y2){ continue; } if(x1 == x2){ ans[i] = 1; continue; } q[i] = {x1 , y1 , x2 , y2}; int v; int id = lower_bound(all(rows), x1) - rows.begin(); if(id == sz(rows)){ continue; } if(rows[id] != x1){ continue; } // cout << i << "FOUND " << endl; id = sz(rows) - 1 - id; int id1 = lower_bound(all(y[id]), y1) - y[id].begin(); if(id1 == sz(y[id])){ continue; } // cout << i << " FOUND " << v << endl; v = P[id][id1]; que[v].pb(i); } for(int i = 0 ; i < n; ++i){ if(!son[i]){ assert(!used[i]); pred[i] = i; dfs(i , 0); } } for(int i = 0; i < t; ++i){ cout << (ans[i] ? "Yes" : "No") << '\n'; } return 0; }
#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...