Submission #287239

#TimeUsernameProblemLanguageResultExecution timeMemory
287239ScarletSNew Home (APIO18_new_home)C++17
0 / 100
5057 ms15164 KiB
#include <bits/stdc++.h> #define ll long long #define sz(x) (int)(x).size(); #define pii pair<int,int> #define f first #define s second using namespace std; const int MAXN=3e5+7; int n,k,x,y,ans,INF=1e9,l,r,m; pair<pii,pii> a[MAXN]; vector<int> present[MAXN]; ll solve() { ans=0; cin>>x>>y; for (int i=1;i<=k;++i) present[i].clear(); for (int i=0;i<n;++i) if (a[i].s.f<=y&&y<=a[i].s.s) present[a[i].f.s].push_back(a[i].f.f); for (int i=1;i<=k;++i) { l=0;r=sz(present[i]); if (!r) return -1; if (x<=present[i][0]) { ans=max(ans,present[i][0]-x); continue; } while (l<r) { m=l+((r-l)>>1); if (present[i][m]<x) l=m+1; else r=m; } ans=max(ans,min(present[i][l]-x,x-present[i][l-1])); } return ans; } int main() { int q; cin>>n>>k>>q; for (int i=0;i<n;++i) cin>>a[i].f.f>>a[i].f.s>>a[i].s.f>>a[i].s.s; sort(a,a+n); while (q--) cout<<solve()<<"\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...
#Verdict Execution timeMemoryGrader output
Fetching results...