Submission #817279

#	Time	Username	Problem	Language	Result	Execution time	Memory
817279		beaconmc	Garden (JOI23_garden)	C++14	6 / 100	3067 ms	51464 KiB

garden

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



#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

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)




int main(){
    fast();
    ll n,m,d;
    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];
    multiset<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]);
    }
    ll prev = -1;
    vector<ll> stuff;
    vector<ll> rem;
    ll ans = 1000000000000000;


    FOR(i,0,d*2){

      if (prev != -1){
        for (auto&j : stuff){
          Y.insert(j);
          rem.push_back(j);
        }
        stuff.clear();

        vector<ll> sussy;
        FOR(i,0,d*2){
          if (Y.count(i%d)) sussy.push_back(0);
          else sussy.push_back(1);
        }
        ll maxi = 0;
        ll noww = 0;
        FOR(i,0,d*2){
          if (sussy[i]==1) noww++;
          else noww = 0;
          maxi = max(maxi, noww);
        }

        ans = min(ans, (d-maxi) * (d-(i-prev-1)));
      }


      if (X[i].size() && X[i][0]==-1){
        prev = i;
        for (auto&j : rem){
          Y.erase(Y.find(j));
        }
        rem.clear();
      }else if (X[i].size()){
        for (auto&j : X[i]){
          stuff.push_back(j);
        }
      }

    }
    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