Submission #965291

#	Time	Username	Problem	Language	Result	Execution time	Memory
965291		Darren0724	Garden (JOI23_garden)	C++17	30 / 100	3076 ms	31828 KiB

garden

#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;
}

• Subtask 1: 0 / 15
• Subtask 2: 6 / 6
• Subtask 3: 8 / 8
• Subtask 4: 16 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25