제출 #830775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
830775		vjudge1	Garden (JOI23_garden)	C++17	100 / 100	1012 ms	108704 KiB

garden

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int dmax = 5e3 + 5, nmax = 5e5 + 5;

int D;

namespace DS { // lista dubla
  #define prev mata
  #define next tactu
  int prev[dmax], next[dmax];
  
  int mx;
  void init(int d) {
    for(int i = 1; i < d; i++) prev[i] = i - 1;
    prev[0] = d - 1;
    for(int i = 0; i < d - 1; i++) next[i] = i + 1;
    next[d - 1] = 0;
    mx = 1;
  }
  void Insert(int x) {
    //cerr << "inserting: " << x << " -> " << prev[x] << " = " << (x - prev[x] + D) % D << '\n';
    if(prev[x] == x) mx = max(mx, D);
    else mx = max(mx, (x - prev[x] + D) % D);
  }
  void Erase(int x) {
    return;
  }
  void erasepoz(int x) {
    //cerr << "erasing " << x << ' ' << prev[9] << ' ' << next[9] << '\n';
    int r = next[x], l = prev[x];
    prev[r] = l;
    next[l] = r;
    Insert(r);
    Insert(l);
  }
  int query() {
    return D - mx + 1;
  }
  #undef prev
  #undef next
}

int whichtype[dmax];
using T = int;

T blablalba[dmax][dmax];
T blablalba2[dmax][dmax];

T& prv1(int x, int y) { return blablalba[y][x]; }
T& prv2(int x, int y) { return blablalba2[y][x]; }

vector<pii> toerase[dmax];
int remain[dmax];

signed main() {
  cin.tie(0) -> sync_with_stdio(0);
  int n, m, d;
  cin >> n >> m >> d;
  D = d;
  for(int i = 0; i < d; i++) whichtype[i] = 0;
  for(int i = 0, x, y; i < n; i++) {
    cin >> x >> y;
    swap(x, y);
    whichtype[y] |= 1;
    prv1(x, y) = 1;
  }
  for(int i = 0, x, y; i < m; i++) {
    cin >> x >> y;
    swap(x, y);
    prv2(x, y) = 1;
    whichtype[y] |= 2;
  }
  
  {
  for(int i = 0; i < d; i++) {
    if((whichtype[i] & 1) == 0) continue;
    int p = d - 1;
    while(prv1(p, i) == 0) p--;
    for(int j = 0; j < d; j++) {
      int u = prv1(j, i);
      prv1(j, i) = p;
      if(u == 1) p = j;
    }
  }
  
  for(int i = 0; i < d; i++) {
    if((whichtype[i] & 2) == 0) continue;
    int p = d - 1;
    while(prv2(p, i) == 0) p--;
    for(int j = 0; j < d; j++) {
      int u = prv2(j, i);
      prv2(j, i) = p;
      if(u == 1) p = j;
    }
  }
  }
  
  
  int mn = d * d;
  
  for(int upperline = 0; upperline < d; upperline++) {
    //cerr << "------------\n";
    DS::init(d);
    int cnt = 0;
    for(int i = 0; i < d; i++) toerase[i].clear();
    
    for(int j = 0; j < d; j++) {
      remain[j] = whichtype[j];
      if(whichtype[j] == 0) { DS::erasepoz(j); continue; }
      //cerr << j << ": " << (int)prv1(upperline, j) << ' ';
      if((whichtype[j] & 1) == 1)
        toerase[prv1(upperline, j)].emplace_back(j, 1), cnt++;
      if((whichtype[j] & 2) == 2)
        toerase[prv2(upperline, j)].emplace_back(j, 2);
    }
    //cerr << '\n';
    
    for(int lowerline = upperline, timp = 1; timp <= d; timp++, lowerline = (lowerline + 1) % d) {
      for(auto [col, val] : toerase[lowerline]) {
        if(val == 1) cnt--;
        else remain[col] ^= val;
        if(remain[col] == 0) DS::erasepoz(col);
      }
      //cerr << upperline << ' ' << lowerline << '\t' << DS::query() << ' ' << cnt << '\t' << DS::query() * timp << '\n';
      if(cnt == 0) mn = min(mn, timp * DS::query());
      
    }
  }
  
  cout << mn << '\n';

}

/**
      Anul asta se da centroid.
-- Surse oficiale
*/

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