Submission #1182094

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182094		noyancanturk	Garden (JOI23_garden)	C++20	6 / 100	337 ms	589240 KiB

garden

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
using pii=pair<int,int>;

const int lim=5005;

#define int int64_t

int havex[lim]{},havey[lim]{};
int parx[lim],pary[lim];
int lenx[lim]{},leny[lim]{};
vector<int>ind[lim][lim],idx[lim],idy[lim];

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,m,D;
  cin>>n>>m>>D;
  for(int i=0;i<n;i++){
    int x,y;
    cin>>x>>y;
    havex[x]=1;
    havey[y]=1;
  }
  int c[m],d[m];
  for(int i=0;i<m;i++){
    cin>>c[i]>>d[i];
    if(havex[c[i]]||havey[d[i]]){
      i--;
      m--;
    }
  }
  for(int i=0;i<D;i++){
    parx[i]=i;
    pary[i]=i;
  }
  for(int i=0;i<D;i++){
    if(!havex[i]&&!havex[(i+D-1)%D])parx[i]=parx[(i+D-1)%D];
    if(!havey[i]&&!havey[(i+D-1)%D])pary[i]=pary[(i+D-1)%D];
  }
  for(int i=0;i<D;i++){
    if(!havex[i]&&!havex[(i+D-1)%D])parx[i]=parx[(i+D-1)%D];
    if(!havey[i]&&!havey[(i+D-1)%D])pary[i]=pary[(i+D-1)%D];
  }
  for(int i=0;i<D;i++){
    lenx[parx[i]]++;
    leny[pary[i]]++;
  }
  for(int i=0;i<m;i++){
    ind[parx[c[i]]][pary[d[i]]].pb(i);
    idx[parx[c[i]]].pb(i);
    idy[pary[d[i]]].pb(i);
  }
  int ans=D*D;
  for(int x=0;x<D;x++){
    if(havex[x]||parx[x]!=x)continue;
    ans=min(ans,D*(D-lenx[x]));
  }
  for(int y=0;y<D;y++){
    if(havey[y]||pary[y]!=y)continue;
    ans=min(ans,D*(D-leny[y]));
  }
  for(int x=0;x<D;x++){
    if(havex[x]||parx[x]!=x)continue;
    for(int y=0;y<D;y++){
      if(havey[y]||pary[y]!=y)continue;
      int lx=D-lenx[x];
      int ly=D-leny[y];
      if(!ind[x][y].size()){
        ans=min(ans,lx*ly);
        continue;
      }
      vector<pii>guys;
      for(int i:ind[x][y]){
        pii toins={c[i],d[i]};
        if(toins.first<x)toins.first+=D;
        if(toins.second<y)toins.second+=D;
        guys.pb(toins);
      }
      sort(guys.begin(),guys.end());
      vector<pii>st;
      for(pii val:guys){
        while(st.size()&&st.back().second<=val.second)st.pop_back();
        st.pb(val);
      }
      ans=min({ans,lx*(ly+st[0].second-y+1),(lx+st.back().first-x+1)*ly});
      for(int i=0;i+1<st.size();i++){
        // cerr<<"here\n";
        // cerr<<x<<' '<<y<<'\n';
        // cerr<<st[i].first<<' '<<st[i+1].second<<'\n';
        ans=min(ans,(lx+st[i].first-x+1)*(ly+st[i+1].second-y+1));
      }
    }
  }
  cout<<ans;
}

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