| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 834971 | sentheta | Garden (JOI23_garden) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "garden.h"
#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);
rep(loop,0,2){
s.clear();
gaps.clear();
rep(i,0,k){
cnt[i] = cntgaps[i] = 0;
}
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;
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;
}