Submission #287216

#TimeUsernameProblemLanguageResultExecution timeMemory
287216ScarletSNew Home (APIO18_new_home)C++17
0 / 100
5069 ms15400 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; while (l<r) { m=l+(r-l)/2; if (present[i][m]<x) l=m+1; else r=m; } if (l==0) ans=max(ans,abs(x-present[i][0])); else ans=max(ans,min(abs(x-present[i][l]),abs(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...