Submission #817895

#	Time	Username	Problem	Language	Result	Execution time	Memory
817895		beaconmc	Garden (JOI23_garden)	C++14	0 / 100	627 ms	28180 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];
    set<ll> Y;

    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.insert(a[i][1]);
    }

    set<ll> stuff;
    set<ll> orig = Y;
    ll ans = 1000000000000000;




    FOR(p,0,d*2){

      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()){
          for (auto&j : X[i]){
            stuff.insert(j);
          }
        }
      }
      if (r<0) break;
      FOR(i,0,d){
        if (!stuff.count(i) && !Y.count(i)){
          insert(i);
        }
      }


      FORNEG(i, r, p){
        if (X[i].size()){
          ans = min(ans, (d-mx) * (d-(i-p-1)));
          for (auto&j : X[i]){
            insert(j);
          }
          

        }
      }

    }
    cout << ans;


    





}

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