Submission #965283

#TimeUsernameProblemLanguageResultExecution timeMemory
965283Darren0724Garden (JOI23_garden)C++17
6 / 100
3031 ms31824 KiB
#include <bits/stdc++.h> using namespace std; #define x first #define y second #define all(x) x.begin(),x.end() #define LCBorz ios_base::sync_with_stdio(false);cin.tie(0); #define endl '\n' const int N=500005; const int D=5005; const int INF=1e9; const int lim=1000; int n,m,d; vector<pair<int,int>> a(N),b(N); int solve(int l){ int r=l,ans=INF; multiset<int> v; for(int i=0;i<n;i++){ if(a[i].x+d<l){ return INF; } else if(a[i].x<l){ r=max(r,a[i].x+d); } else{ r=max(r,a[i].x); } v.insert(a[i].y); } vector<int> e[D]; for(int i=0;i<m;i++){ if((b[i].x<l&&b[i].x+d>r)||l>b[i].x+d||r<b[i].x){ v.insert(b[i].y); e[b[i].x].push_back(b[i].y); e[b[i].x+d].push_back(b[i].y); } } int mx=0; for(auto it=v.begin();it!=v.end();){ auto it1=next(it); if(it1==v.end())break; mx=max(mx,*it1-*it-1); it=it1; } mx=max(mx,*v.begin()+d-*(prev(v.end()))-1); ans=(d-mx)*(r-l+1); //cout<<l<<' '<<r<<' '<<ans<<endl; for(int i=r+1;i<l+d;i++){ for(int j:e[i]){ auto it=v.lower_bound(j); int a=(it==v.begin()?*prev(it):*(prev(v.end()))); int b=(it==prev(v.end())?*next(it):*v.begin()); if(a>b)b+=d; mx=max(mx,b-a-1); } ans=min(ans,(d-mx)*(i-l+1)); } return ans; } int32_t main(){ LCBorz; cin>>n>>m>>d; for(int i=0;i<n;i++){ cin>>a[i].x>>a[i].y; } for(int i=0;i<m;i++){ cin>>b[i].x>>b[i].y; } int ans=INF; for(int i=0;i<d;i++){ ans=min(ans,solve(i)); } cout<<ans<<endl; 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...
#Verdict Execution timeMemoryGrader output
Fetching results...