Submission #834972

#	Time	Username	Problem	Language	Result	Execution time	Memory
834972		sentheta	Garden (JOI23_garden)	C++17	100 / 100	115 ms	17728 KiB

garden

#include<bits/stdc++.h>
using namespace std;

#define V vector
#define rep(i,a,b) for(int i=(int)(a); i<(int)(b); i++)
#define Int long long
#define all(x) (x).begin(), (x).end()

#if VANWIJ
	#define DBG 1
#else
	#define DBG 0
#endif
#define cerr if(DBG) cout
#define dbg(x) cerr << "?" << #x << " : " << x << endl;



// van Emde Boas tree. Maintains a set of integers in range [0, 2^B) and supports operations
//	findNext(i): returns minimum j >= i in set, or 2^B if none exist
// findPrev(i): returns maximum j <= i in set, or -1 if none exist
//	insert(i), erase(i): insert/erase i into the set
//	empty(): returns TRUE if the set is empty
//	clear(): empties the set
//	init(bts): inits the set, after the call i will be in the set if bts[i] = 1. bts should be a bitset, but can be a vector of 0/1
// All operations except empty, clear and init are O(log B) = O(log log 2^B) with good constants

// example: VEBTree<17> s;
// REMEMBER TO CALL s.clear() BEFORE USING

// source : https://judge.yosupo.jp/submission/76699
#define ull unsigned long long

template<int B, typename ENABLE = void>
class VEBTree {
	private:
		const static int K = B/2, R = (B+1)/2, M = (1<<B);
		const static int S = 1<<K, MASK = (1<<R)-1;
		array<VEBTree<R>,S> ch;
		VEBTree<K> act;
		int mi, ma;
	public:
		bool empty() const{return ma<mi;}
		
		int findNext(int i) const{
			if(i <= mi) return mi;
			if(i > ma) return M;
			
			int j = i>>R, x = i&MASK;
			int res = ch[j].findNext(x);
			if(res<=MASK) return (j<<R) + res;
			
			j=act.findNext(j + 1);
			return (j>=S) ? ma : ((j<<R) + ch[j].findNext(0));
		}
		int findPrev(int i) const {
			if(i >= ma) return ma;
			if(i < mi) return -1;
			
			int j = i>>R, x = i & MASK;
			int res = ch[j].findPrev(x);
			if(res >= 0) return (j<<R) + res;
			
			j = act.findPrev(j - 1);
			return (j < 0) ? mi : ((j<<R) + ch[j].findPrev(MASK));
		}
		void insert(int i) {
			if(i <= mi) {
				if(i == mi) return;
				swap(mi, i);
				if(i == M) ma = mi; // we were empty
				if(i >= ma) return; // we had mi == ma
			} else if(i >= ma) {
				if(i == ma) return;
				swap(ma, i);
				if(i <= mi) return; // we had mi == ma
			}
			int j = i>>R;
			if(ch[j].empty()) act.insert(j);
			ch[j].insert(i & MASK);
		}
		void erase(int i) {
			if(i <= mi) {
				if(i < mi) return;
				i = mi = findNext(mi + 1);
				if(i >= ma) {
					if(i > ma) ma = -1; // we had mi == ma
					return; // after erase we have mi == ma
				}
			} else if(i >= ma) {
				if(i > ma) return;
				i = ma = findPrev(ma - 1);
				if(i <= mi) return; // after erase we have mi == ma
			}
			int j = i>>R;
			ch[j].erase(i & MASK);
			if(ch[j].empty()) act.erase(j);
		}

		void clear() {
			mi = M, ma = -1;
			act.clear();
			for (int i = 0; i < S; ++i) ch[i].clear();
		}
		template<class T>
		void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
			s0 = -shift + bts.findNext(shift + s0, shift + M-1 - s1);
			s1 = M-1 - (-shift + bts.findPrev(shift + M-1-s1, shift + s0));
			if(s0 + s1 >= M) clear();
			else {
				act.clear();
				mi = s0, ma = M-1 - s1;
				++s0; ++s1;
				for (int j = 0; j < S; ++j) {
					ch[j].init(bts, shift + (j<<R), max(0, s0 - (j<<R)), max(0, s1 - ((S-1-j)<<R)));
					if(! ch[j].empty()) act.insert(j);
				}
			}
		}
};

template<int B>
class VEBTree<B, enable_if_t<(B <= 6)>> {
	private:
		const static int M = (1<<B);
		ull act;
	public:
		bool empty() const { return !act; }
		void clear() { act = 0; }

		int findNext(int i) const {
			return ((i < M) && (act>>i)) ? i + __builtin_ctzll(act>>i) : M;
		}
		int findPrev(int i) const {
			return ((i != -1) && (act<<(63 - i))) ? i - __builtin_clzll(act<<(63 - i)) : -1;
		}
		void insert(int i) { act |= 1ull<<i; }
		void erase(int i) { act &= ~(1ull<<i); }
		
		template<class T>
		void init(const T& bts, int shift = 0, int s0 = 0, int s1 = 0) {
			if(s0 + s1 >= M) act = 0;
			else act = bts.getRange(shift + s0, shift + M-1-s1)<<s0;
		}
};



const int INF = 1e9;
const int N = 5e5+5;
const int K = 5005;

int n, m, k;
V<int> a, b, c, d;


V<int> byx[2*K];

int ans = INF;



bool inside(int l,int x,int r){
	return (l<=x && x<=r) || (l<=x+k && x+k<=r);
}


const int LK = 13;

// set of must-have y's
// set<int> s;
VEBTree<LK> s;
int cnt[K];

// set of gaps between must-have y
// set<int> gaps;
VEBTree<LK> gaps;
int cntgaps[K];
void gap_insert(int val){
	cntgaps[val]++;
	if(cntgaps[val]==1){
		gaps.insert(val);
	}
}
void gap_erase(int val){
	cntgaps[val]--;
	if(cntgaps[val]==0){
		gaps.erase(val);
	}
}

void insert(int y){
	cnt[y]++;
	if(cnt[y]!=1) return;
	
	int l=s.findPrev(y), r=s.findNext(y);
	s.insert(y);
	
	if(l!=-1 && r!=1LL<<LK){
		gap_erase(r-l);
	}
	if(l!=-1){
		gap_insert(y-l);
	}
	if(r!=1LL<<LK){
		gap_insert(r-y);
	}
}
void erase(int y){
	cnt[y]--;
	if(cnt[y]!=0) return;
	
	s.erase(y);
	int l=s.findPrev(y), r=s.findNext(y);
	
	if(l!=-1 && r!=1LL<<LK){
		gap_insert(r-l);
	}
	if(l!=-1){
		gap_erase(y-l);
	}
	if(r!=1LL<<LK){
		gap_erase(r-y);
	}
}
// get optimal width
int getWidth(){
	int ret = k-gaps.findPrev((1LL<<LK)-1)+1;
	ret = min(ret, s.findPrev((1LL<<LK)-1)-s.findNext(0)+1);
	return ret;
}



int minimum_cells(int _n,int _m,int _k,V<int>_a,V<int>_b,V<int>_c,V<int>_d){
	n = _n; m = _m; k = _k;
	a.swap(_a); b.swap(_b); c.swap(_c); d.swap(_d);
	
	// A[i] or B[i]
	// C[i] and D[i]
	
	// flip X and Y in second loop
	rep(loop,0,2){
		
		s.clear();
		gaps.clear();
		rep(i,0,k){
			cnt[i] = cntgaps[i] = 0;
		}
		
		// insert needed Y
		bool vx[k];
		rep(i,0,k) vx[i] = 0;
		rep(i,0,n){
			vx[a[i]] = 1;
			insert(b[i]);
		}
		
		rep(i,0,k){
			byx[i].clear();
		}
		rep(i,0,m){
			byx[c[i]].push_back(i);
		}

		// cerr << "Y-GAP" << endl;
		// for(int y : s) cerr << y << " ";
		// cerr << endl;
		// for(int gap : gaps) cerr << gap << " ";
		// cerr << endl;
		
		// iterate all possible X gaps
		
		int first=-1, last=-1;
		rep(i,0,k) if(vx[i]){
			if(first==-1) first = i;
			if(last!=-1){
				
				// check(i, last+k);
				for(int x=(last+1)%k; x!=i; /*x=(x+1)%k*/){
					for(int j : byx[x]) insert(d[j]);
						
					x++;
					if(x==k) x=0;
				}
				ans = min(ans, (k+last-i+1)*getWidth());
				for(int x=(last+1)%k; x!=i; /*x=(x+1)%k*/){
					for(int j : byx[x]) erase(d[j]);
					
					x++;
					if(x==k) x=0;
				}
			
			}
			last = i;
		}
		
		// check(first, last);
		for(int x=(last+1)%k; x!=first; x=(x+1)%k){
			for(int j : byx[x]) insert(d[j]);
		}
		ans = min(ans, (last-first+1)*getWidth());
		for(int x=(last+1)%k; x!=first; x=(x+1)%k){
			for(int j : byx[x]) erase(d[j]);
		}
		
		a.swap(b);
		c.swap(d);
	}
	
	
	
		
	return ans;
}



int main() {
  int N, M, D;
  assert(3 == scanf("%d %d %d", &N, &M, &D));
  std::vector<int> P(N), Q(N), R(M), S(M);
  for (int i = 0; i < N; ++i) {
    assert(2 == scanf("%d %d", &P[i], &Q[i]));
  }
  for (int j = 0; j < M; ++j) {
    assert(2 == scanf("%d %d", &R[j], &S[j]));
  }

  printf("%d\n", minimum_cells(N, M, D, P, Q, R, S));
}

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