Submission #965312

#	Time	Username	Problem	Language	Result	Execution time	Memory
965312		Darren0724	Garden (JOI23_garden)	C++17	0 / 100	322 ms	34612 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,mx1=0;
multiset<int> v;
vector<pair<int,int>> a(N),b(N);
vector<int> t(D);
vector<int> e[D];
int r=0;
int solve(int l){
    int ans=INF;
    if(t[l])r=l+d-1;
    
    vector<int> tim;
    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);
            if(b[i].x>r)tim.push_back(b[i].x);
            if(b[i].x+d>r)tim.push_back(b[i].x+d);
        }
    }
    sort(all(tim));
    tim.resize(unique(all(tim))-tim.begin());
    int mx=mx1;
    mx=max(mx,*v.begin()+d-*(prev(v.end()))-1);
    ans=(d-mx)*(r-l+1);
    //cout<<l<<' '<<r<<' '<<ans<<endl;
    for(int i:tim){
        if(i>=l+d)break;
        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));
    }
    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){
            e[b[i].x].clear();
            e[b[i].x+d].clear();
        }
    }
    return ans;
}
int32_t main(){
    LCBorz;
    cin>>n>>m>>d;
    for(int i=0;i<n;i++){
        cin>>a[i].x>>a[i].y;
        //a[i].x=i%d,a[i].y=i/d;
        v.insert(a[i].y);
        t[a[i].x+1]=1;
        r=max(r,a[i].x);
    }
    for(auto it=v.begin();it!=v.end();){
        auto it1=next(it);
        if(it1==v.end())break;
        mx1=max(mx1,*it1-*it-1);
        it=it1;
    }
    for(int i=0;i<m;i++){
        cin>>b[i].x>>b[i].y;
        //a[i].x=i%d,a[i].y=i%d;
    }
    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: 0 / 6
• Subtask 3: 0 / 8
• Subtask 4: 0 / 16
• Subtask 5: 0 / 30
• Subtask 6: 0 / 25