제출 #355041

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
355041		ryansee	식물 비교 (IOI20_plants)	C++14	27 / 100	4062 ms	145232 KiB

plants

#include "plants.h"
 
#include "bits/stdc++.h"
using namespace std;
 
#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr<<"hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return rng() % (y+1-x) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }
 
using ll=long long; 
using ld=long double;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
using pi=pair<ll,ll>; using spi=pair<ll,pi>; using dpi=pair<pi,pi>; 
 
long long LLINF = 1e18;
int INF = 1e9+1e6;
#define MAXN (200002)
 
int n, start, k;
vector<int> R;
ll A[MAXN];
inline ll cy(ll x) {
	x %= n, x += n, x %= n; return x;
}
ll dist(int x,int y) {
	if(x > y) swap(x, y);
	return min(y-x, n-y+x);	
}

struct node {
	int s,e,m;
	spi v;
	ll lazy[3];
	node*l,*r;
	node(int S,int E){
		s=S,e=E,m=(s+e)>>1;
		v=spi(LLINF, pi(0, -1)), mmst(lazy, 0);
		if(s^e)l=new node(s,m),r=new node(m+1,e),v=min(l->v,r->v);
		else v=spi(R[s], pi(0, s));
	}
	void value() {
		v.f += lazy[0], v.s.f += lazy[1];
		if(s^e) FOR(i,0,1) l->lazy[i]+=lazy[i], r->lazy[i]+=lazy[i];
		lazy[0]=lazy[1]=0;
	}
	void update(int x,int y,pi nval) {
		if(s==x&&e==y) {
			if(nval.s <= 1) lazy[nval.s] += nval.f;
			else lazy[nval.s] = max(lazy[nval.s], nval.f);
			return;
		}
		if(x>m) r->update(x,y,nval);
		else if(y<=m) l->update(x,y,nval);
		else l->update(x,m,nval),r->update(m+1,y,nval);
		l->value(), r->value();
		v=min(l->v,r->v);
	}
	spi rmq(int x,int y) {
		value();
		if(s==x&&e==y) return v;
		if(x>m) return r->rmq(x,y);
		else if(y<=m) return l->rmq(x,y);
		else return min(l->rmq(x,m),r->rmq(m+1,y));
	}
	void set(int x,ll add=0) {
		value();
		add = max(add, lazy[2]);
		if(s==e) {
			A[s] = add;
			v = spi(LLINF, pi(0, -1));
			return;
		}
		if(x>m) r->set(x, add);
		else l->set(x, add);
		l->value(), r->value();
		v = min(l->v, r->v);
	}
} *seg;
void update(int x,int y,pi nval) {
	x=cy(x), y=cy(y);
	if(x<=y) seg->update(x,y,nval);
	else seg->update(x,n-1,nval), seg->update(0,y,nval);
}
spi rmq(int x,int y) {
	x=cy(x), y=cy(y);
	if(x<=y) return seg->rmq(x, y);
	else return min(seg->rmq(x, n-1), seg->rmq(0, y));
}
struct node2 {
	int s,e,m;
	array<pi, 2> v;
	node2*l,*r;
	node2(int S,int E){
		s=S,e=E,m=(s+e)>>1;
		v = {pi(INF, -1), pi(-INF, -1)};
		if(s^e)l=new node2(s,m),r=new node2(m+1,e);
	}
	array<pi, 2> comb(array<pi, 2> x,array<pi, 2> y) {
		return array<pi, 2> {min(x[0], y[0]), max(x[1], y[1])};
	}
	array<pi, 2> rmq(int x,int y) {
		if(s==x&&e==y) return v;
		if(x>m) return r->rmq(x, y);
		else if(y<=m) return l->rmq(x, y);
		else return comb(l->rmq(x, m), r->rmq(m+1, y));
	}
	ll mx(int x,int y) {
		x = cy(x), y = cy(y);
		if(x <= y) return rmq(x, y)[1].s;
		else return max(rmq(x, n-1)[1], rmq(0, y)[1]).s;
	}
	ll mi(int x,int y) {
		x = cy(x), y = cy(y);
		if(x <= y) return rmq(x, y)[0].s;
		else return min(rmq(x, n-1)[0], rmq(0, y)[0]).s;
	}
	void set(int x) {
		if(s==e) {
			v = {pi(A[s], s), pi(A[s], s)};
			return;
		}
		if(x>m) r->set(x);
		else l->set(x);
		v = comb(l->v, r->v);
	}
} *seg2;
struct tree {
	int st[MAXN], en[MAXN];
	bitset<MAXN> r;
	vector<int> v[MAXN];
	tree() {
		mmst(st, 0), mmst(en, 0), r.set();
		for(auto&i:v) assert(i.empty());
	}
	void add(int x,int y) {
		if(y==-1||x==y) return;
		r[x]=0, v[y].eb(x);
	}
	void solve() {
		ll co=1;
		function<void(ll)>dfs=[&](int x) {
			st[x]=co++;
			for(auto i:v[x]) dfs(i);
			en[x]=co-1;
		};
		FOR(i,0,n-1) if(r[i]) dfs(i);
	}
	bool isp(int a,int b) { return st[a]<=st[b]&&en[a]>=en[b]; }
} t[2];
void init(int K, std::vector<int> r) { k=K, R=r;
	n=r.size();
	seg=new node(0, n-1);
	FOR(i,0,n-1) if(r[i]==0) update(i+1, i+k-1, pi(1, 1));
	while(1) {
		start = seg->rmq(0, n-1).s.s;
		if(start == -1) break;
		seg->set(start);
		update(start+1, start+k-1, pi(A[start]+1, 2));
		update(start+1, start+k-1, pi(-1, 1));
		update(start-k+1, start-1, pi(A[start]+1, 2));
		update(start-k+1, start-1, pi(-1, 0));
		vector<int> tmp;
		while(1) {
			spi x = rmq(start-k+1, start-1);
			if(x.f == 0) {
				tmp.eb(x.s.s);
				update(x.s.s+1, x.s.s+k-1, pi(1, 1));
				update(x.s.s, x.s.s, pi(1, 0));
			} else break;
		}
		for(auto i:tmp) update(i, i, pi(-1, 0));
	}
	/* dp[0][0]=dp[1][0]=1;
	FOR(i,0,1) fw[i].update(A[0], 1);
	FOR(i,1,n-1) {
		// FOR(jj,i-k+1,i-1) { int j=cy(jj);
			// assert(A[i] ^ A[j]);
			// if(A[i] < A[j]) dp[0][i] |= dp[0][j];
			// else dp[1][i] |= dp[1][j];
		// }
		if(i >= k) FOR(j,0,1) if(dp[j][i-k]) fw[j].update(A[i-k], -1);
		dp[0][i] = fw[0].sum(A[i]+1, MAXN-2) > 0;
		dp[1][i] = fw[1].sum(0, A[i]-1) > 0;
		FOR(j,0,1) if(dp[j][i]) fw[j].update(A[i], 1);
	}
	fw[0]=fen(), fw[1]=fen();
	dp2[0][0]=dp2[1][0]=1;
	FOR(i,0,1) fw[i].update(A[0], 1);
	DEC(ii,-1,-n+1) { int i=cy(ii);
		// FOR(jj,i+1,i+k-1) { int j=cy(jj);
			// assert(A[i] ^ A[j]);
			// if(A[i] < A[j]) dp2[0][i] |= dp2[0][j];
			// else dp2[1][i] |= dp2[1][j];
		// }
		int t = cy(i + k);
		if(t > i || t == 0) {
			FOR(j,0,1) if(dp2[j][t]) fw[j].update(A[t], -1);
		}
		dp2[0][i] = fw[0].sum(A[i]+1, MAXN-2) > 0;
		dp2[1][i] = fw[1].sum(0, A[i]-1) > 0;
		FOR(j,0,1) if(dp2[j][i]) fw[j].update(A[i], 1);
	} */
	
	vector<int> p;
	FOR(i,0,n-1) p.eb(i);
	sort(all(p), [](int x,int y){return A[x]<A[y];});
	seg2=new node2(0, n-1);
	for(auto i:p) {
		int target = seg2->mx(i, i+k-1); // connect to shortest tower within k that is taller than you
		t[0].add(i, target);
		seg2->set(i);
	}
	
	sort(all(p), [](int x,int y){return A[x]>A[y];});
	seg2=new node2(0, n-1);
	for(auto i:p) {
		int target = seg2->mi(i, i+k-1);
		t[1].add(i, target);
		seg2->set(i);
	}
	// FOR(i,0,n-1) {
		// int target = seg2->mi(i, i-k+1);
		// t[2].add(i, target);
	// }
	// FOR(i,0,n-1) {
		// int target = seg2->mx(i, i-k+1);
		// t[3].add(i, target);
	// }
	FOR(i,0,1) t[i].solve();
}
int compare_plants(int x, int y) {
	/* if(x == 0) {
		if(dp[0][y] || dp2[0][y]) return -1;
		else if(dp[1][y] || dp2[1][y]) return 1;
		else return 0;
	}
	if(n > 300 || reach[x][y] || reach[y][x]) return A[x] < A[y] ? 1 : -1;
	else return 0; */
	
	if(dist(x, y) < k) {
		return A[x] < A[y] ? 1 : -1;
	}
	
	FOR(ii,y,y+k-1) { int i=cy(ii);
		if(A[y] <= A[i]) {
			if(t[0].isp(i, x)) { assert(A[i] < A[x]); return -1; }
		}
	}
	FOR(ii,y,y+k-1) { int i=cy(ii);
		if(A[y] >= A[i]) {
			if(t[1].isp(i, x)) { assert(A[x] < A[i]); return 1; }
		}
	}
	swap(x, y);
	FOR(ii,y,y+k-1) { int i=cy(ii);
		if(A[y] <= A[i]) {
			if(t[0].isp(i, x)) { assert(A[i] < A[x]); return 1; }
		}
	}
	FOR(ii,y,y+k-1) { int i=cy(ii);
		if(A[y] >= A[i]) {
			if(t[1].isp(i, x)) { assert(A[x] < A[i]); return -1; }
		}
	}
	
	assert(0);
	return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 14 / 14
• Subtask 3: 13 / 13
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 15
• Subtask 7: 0 / 25