Submission #830741

#	Time	Username	Problem	Language	Result	Execution time	Memory
830741		vjudge1	Garden (JOI23_garden)	C++17	15 / 100	625 ms	107956 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 freq[nmax];
  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;
    prev[d + 1] = 0;
    mx = 1;
  }
  void Insert(int x) {
    if(prev[x] == x) mx = max(mx, D);
    else mx = max(mx, (x - prev[x] + D) % D);
  }
  void Erase(int x) {
    // laba
    return;
  }
  void erasepoz(int x) {
    //cerr << "erase " << x << '\t' << "inserting " << '\n';;
    prev[next[x]] = prev[x];
    next[prev[x]] = next[x];
    Insert(next[x]);
    Insert(prev[x]);
  }
  int query() {
    return D - mx + 1;
  }
  #undef prev
  #undef next
}

int whichtype[dmax];
using T = int;
//vector<int> typea[dmax];
//vector<int> typeb[dmax];
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());
      //if(mn == 1953) {
        //exit(0);
      //}
    }
  }
  
  cout << mn << '\n';

}

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

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