oj.uz

답안 #354985

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
354985 2021-01-22T07:56:45 Z ryansee 식물 비교 (IOI20_plants) C++14
32 / 100
 3729 ms 145376 KB 
#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;
	}
	
	if(t[0].isp(y, x)) return -1;
	if(t[1].isp(y, x)) return 1;
	if(t[0].isp(x, y)) return 1;
	if(t[1].isp(x, y)) return -1;
	return 0;
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 10 ms 12856 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 73 ms 15724 KB Output is correct
7 Correct 170 ms 26928 KB Output is correct
8 Correct 1319 ms 126540 KB Output is correct
9 Correct 1270 ms 126688 KB Output is correct
10 Correct 1157 ms 126816 KB Output is correct
11 Correct 1078 ms 128600 KB Output is correct
12 Correct 1029 ms 133092 KB Output is correct
13 Correct 920 ms 138976 KB Output is correct
14 Correct 1155 ms 139056 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 10 ms 12928 KB Output is correct
6 Correct 18 ms 13548 KB Output is correct
7 Correct 117 ms 18924 KB Output is correct
8 Correct 11 ms 13036 KB Output is correct
9 Correct 17 ms 13548 KB Output is correct
10 Correct 114 ms 18924 KB Output is correct
11 Correct 99 ms 18796 KB Output is correct
12 Correct 101 ms 19052 KB Output is correct
13 Correct 112 ms 19052 KB Output is correct

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 10 ms 12928 KB Output is correct
6 Correct 18 ms 13548 KB Output is correct
7 Correct 117 ms 18924 KB Output is correct
8 Correct 11 ms 13036 KB Output is correct
9 Correct 17 ms 13548 KB Output is correct
10 Correct 114 ms 18924 KB Output is correct
11 Correct 99 ms 18796 KB Output is correct
12 Correct 101 ms 19052 KB Output is correct
13 Correct 112 ms 19052 KB Output is correct
14 Correct 296 ms 27756 KB Output is correct
15 Correct 3729 ms 136912 KB Output is correct
16 Correct 293 ms 27884 KB Output is correct
17 Correct 3723 ms 137544 KB Output is correct
18 Correct 1760 ms 142176 KB Output is correct
19 Correct 1919 ms 142160 KB Output is correct
20 Correct 2978 ms 145376 KB Output is correct

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 11 ms 12908 KB Output is correct
2 Correct 10 ms 13056 KB Output is correct
3 Incorrect 82 ms 16876 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 13 ms 12908 KB Output is correct
5 Incorrect 11 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Incorrect 16 ms 13548 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 10 ms 12856 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Correct 9 ms 12908 KB Output is correct
6 Correct 73 ms 15724 KB Output is correct
7 Correct 170 ms 26928 KB Output is correct
8 Correct 1319 ms 126540 KB Output is correct
9 Correct 1270 ms 126688 KB Output is correct
10 Correct 1157 ms 126816 KB Output is correct
11 Correct 1078 ms 128600 KB Output is correct
12 Correct 1029 ms 133092 KB Output is correct
13 Correct 920 ms 138976 KB Output is correct
14 Correct 1155 ms 139056 KB Output is correct
15 Correct 10 ms 12908 KB Output is correct
16 Correct 9 ms 12908 KB Output is correct
17 Correct 9 ms 12908 KB Output is correct
18 Correct 9 ms 12908 KB Output is correct
19 Correct 10 ms 12928 KB Output is correct
20 Correct 18 ms 13548 KB Output is correct
21 Correct 117 ms 18924 KB Output is correct
22 Correct 11 ms 13036 KB Output is correct
23 Correct 17 ms 13548 KB Output is correct
24 Correct 114 ms 18924 KB Output is correct
25 Correct 99 ms 18796 KB Output is correct
26 Correct 101 ms 19052 KB Output is correct
27 Correct 112 ms 19052 KB Output is correct
28 Correct 296 ms 27756 KB Output is correct
29 Correct 3729 ms 136912 KB Output is correct
30 Correct 293 ms 27884 KB Output is correct
31 Correct 3723 ms 137544 KB Output is correct
32 Correct 1760 ms 142176 KB Output is correct
33 Correct 1919 ms 142160 KB Output is correct
34 Correct 2978 ms 145376 KB Output is correct
35 Correct 11 ms 12908 KB Output is correct
36 Correct 10 ms 13056 KB Output is correct
37 Incorrect 82 ms 16876 KB Output isn't correct
38 Halted 0 ms 0 KB -