이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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=10005;
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);
v.erase(it);
}
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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |