Submission #639159

#TimeUsernameProblemLanguageResultExecution timeMemory
639159Dec0DeddTrampoline (info1cup20_trampoline)C++14
100 / 100
1143 ms82400 KiB
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define pp pair<pii, int> const int N = 2e5+10; const int K = 20; vector<int> G[N]; pii p[N]; set<pii> s[N]; int r, c, n, indeg[N], up[N][K+1]; void dfs(int v, int p) { up[v][0]=p; for (int i=1; i<=K; ++i) up[v][i]=up[up[v][i-1]][i-1]; for (auto u : G[v]) { if (u == p) continue; dfs(u, v); } } int fv(int i, int x) { for (int k=K; k>=0; --k) { int idx=up[i][k]; if (p[idx].first < x) i=idx; } return i; } void solve() { ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL); cin>>r>>c>>n; set<int> st; map<int, int> sc; for (int i=1; i<=n; ++i) { int a, b; cin>>a>>b; p[i]={a, b}; st.insert(a); } int i=1; for (auto u : st) sc[u]=i++; for (int i=1; i<=n; ++i) s[sc[p[i].first]].insert({p[i].second, i}); for (int i=1; i<=n; ++i) { int a=p[i].first, b=p[i].second; if (sc.find(a+1) == sc.end()) continue; int nxt=sc[a+1]; a=sc[a]; auto ptr=s[nxt].lower_bound({b, -1}); if (ptr == s[nxt].end()) continue; G[ptr->second].push_back(i); ++indeg[i]; } for (int i=1; i<=n; ++i) { if (indeg[i] == 0) dfs(i, i); } int q; cin>>q; for (int i=1; i<=q; ++i) { int is, js, ie, je; cin>>is>>js>>ie>>je; if (js > je) cout<<"No\n"; else if (is == ie) cout<<"Yes\n"; else { if (sc.find(is) == sc.end()) { cout<<"No\n"; continue; } is=sc[is]; auto ptr=s[is].lower_bound({js, -1}); if (ptr == s[is].end()) { cout<<"No\n"; continue; } int f=fv(ptr->second, ie); if (p[f].first == ie-1 && p[f].second <= je) cout<<"Yes\n"; else cout<<"No\n"; } } for (int i=1; i<=n; ++i) s[i].clear(), G[i].clear(), indeg[i]=0; } int main() { 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...