Submission #817916

#	Time	Username	Problem	Language	Result	Execution time	Memory
817916		beaconmc	Garden (JOI23_garden)	C++14	100 / 100	1942 ms	41280 KiB

garden

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>



typedef long long ll;
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i, x, y) for(ll i=x; i<y; i++)
#define FORNEG(i, x, y) for(ll i=x; i>y; i--)
//#define ordered_set tree<ll, null_type,less_equal<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define fast() ios_base::sync_with_stdio(false);cin.tie(NULL)


ll n,m,d;

ll cc[5001];
ll sz[5001];
ll mx = 0;

ll find(ll a){
  while (cc[a]!=a) cc[a]=cc[cc[a]],a=cc[a];
  return a;
}

void unite(ll a,ll b){
  ll A = find(a), B = find(b);
  if (A==B) return;
  sz[B] += sz[A];
  cc[A] = B;
  mx = max(mx, sz[B]);
}

void insert(ll a){
  sz[a] = max(sz[a], (ll) 1);
  mx = max(mx, (ll) 1);


  if (sz[(a-1+d)%d]) unite((a-1+d)%d, a);
  if (sz[(a+1+d)%d]) unite((a+1+d)%d, a);
}



int main(){
    FOR(i,0,5001) cc[i] = i, sz[i]=0;

    fast();
    
    cin >> n >> m >> d;
    vector<vector<ll>> a,b;

    FOR(i,0,n){
      vector<ll> temp(2);
      cin >> temp[0] >> temp[1];
      a.push_back(temp);
    }

    FOR(i,0,m){
      vector<ll> temp(2);
      cin >> temp[0] >> temp[1];
      b.push_back(temp);
    }

    vector<ll> X[10001];
    bool Y[5001];

    FOR(i,0,m){
      X[b[i][0]].push_back(b[i][1]);
      X[b[i][0]+d].push_back(b[i][1]);
    }
    FOR(i,0,n){
      X[a[i][0]] = {-1};
      X[a[i][0]+d] = {-1};
      Y[a[i][1]] = 1;
    }


    ll ans = 1000000000000000;




    FORNEG(p, d*2-1,-1){
      bool stuff[5001];
      FOR(i,0,5001) stuff[i]=0;

      FOR(i,0,5001) cc[i] = i, sz[i]=0;
      mx = 0;

      ll r = -1;
      FOR(i,p+1,d*2){
        if (X[i].size() && X[i][0]==-1){
          r = i;
          break;
        }else if (X[i].size()){
          vector<ll> temp;
          for (auto&j : X[i]){
            if (stuff[j] == 0){
              temp.push_back(j);
              stuff[j]=1;
            }
          }
          X[i] = temp;
        }
      }


      FOR(i,0,d){
        if (!stuff[i] && !Y[i]){
          insert(i);
        }

      }



      FORNEG(i, r, p){

        if (X[i].size() && X[i][0] != -1){
          for (auto&j : X[i]){
            if (!Y[j]) insert(j);
          }
        }

        ans = min(ans, (d-mx) * (d-(i-p-1)));
      


      }

    }
    cout << ans;


/*
895
973
1764
2280
3197
*/





}

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