oj.uz

Submission #355044

# Submission time Handle Problem Language Result Execution time Memory
355044 2021-01-22T08:29:28 Z ryansee Comparing Plants (IOI20_plants) C++14
43 / 100
 4000 ms 145144 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;
	}
	
	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-k+1,y) { 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-k+1,y) { int i=cy(ii);
		if(A[y] >= A[i]) {
			if(t[1].isp(i, x)) { assert(A[x] < A[i]); return -1; }
		}
	}
	
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13036 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 9 ms 12908 KB Output is correct
6 Correct 79 ms 15724 KB Output is correct
7 Correct 177 ms 26964 KB Output is correct
8 Correct 1344 ms 126556 KB Output is correct
9 Correct 1260 ms 126432 KB Output is correct
10 Correct 1242 ms 126688 KB Output is correct
11 Correct 1081 ms 128736 KB Output is correct
12 Correct 1040 ms 132888 KB Output is correct
13 Correct 939 ms 138944 KB Output is correct
14 Correct 1110 ms 138928 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 10 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 12908 KB Output is correct
6 Correct 17 ms 13548 KB Output is correct
7 Correct 125 ms 18924 KB Output is correct
8 Correct 12 ms 13036 KB Output is correct
9 Correct 17 ms 13548 KB Output is correct
10 Correct 115 ms 18924 KB Output is correct
11 Correct 126 ms 18824 KB Output is correct
12 Correct 148 ms 19052 KB Output is correct
13 Correct 113 ms 19052 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 10 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 12908 KB Output is correct
6 Correct 17 ms 13548 KB Output is correct
7 Correct 125 ms 18924 KB Output is correct
8 Correct 12 ms 13036 KB Output is correct
9 Correct 17 ms 13548 KB Output is correct
10 Correct 115 ms 18924 KB Output is correct
11 Correct 126 ms 18824 KB Output is correct
12 Correct 148 ms 19052 KB Output is correct
13 Correct 113 ms 19052 KB Output is correct
14 Correct 292 ms 27756 KB Output is correct
15 Correct 3675 ms 136960 KB Output is correct
16 Correct 286 ms 27884 KB Output is correct
17 Correct 3663 ms 137424 KB Output is correct
18 Correct 1797 ms 142008 KB Output is correct
19 Correct 1909 ms 142048 KB Output is correct
20 Correct 2952 ms 145144 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 10 ms 12908 KB Output is correct
3 Correct 116 ms 16876 KB Output is correct
4 Correct 1324 ms 132320 KB Output is correct
5 Correct 2142 ms 130528 KB Output is correct
6 Execution timed out 4077 ms 131296 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 9 ms 12908 KB Output is correct
3 Correct 8 ms 12908 KB Output is correct
4 Correct 10 ms 12908 KB Output is correct
5 Correct 11 ms 12908 KB Output is correct
6 Correct 13 ms 13164 KB Output is correct
7 Correct 46 ms 14060 KB Output is correct
8 Correct 42 ms 14184 KB Output is correct
9 Correct 37 ms 14060 KB Output is correct
10 Correct 39 ms 14060 KB Output is correct
11 Correct 39 ms 14060 KB Output is correct
12 Correct 43 ms 14060 KB Output is correct
13 Correct 24 ms 14060 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 12908 KB Output is correct
2 Correct 8 ms 12908 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 8 ms 12908 KB Output is correct
5 Correct 17 ms 13444 KB Output is correct
6 Correct 3230 ms 131028 KB Output is correct
7 Execution timed out 4085 ms 131296 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13036 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 9 ms 12908 KB Output is correct
6 Correct 79 ms 15724 KB Output is correct
7 Correct 177 ms 26964 KB Output is correct
8 Correct 1344 ms 126556 KB Output is correct
9 Correct 1260 ms 126432 KB Output is correct
10 Correct 1242 ms 126688 KB Output is correct
11 Correct 1081 ms 128736 KB Output is correct
12 Correct 1040 ms 132888 KB Output is correct
13 Correct 939 ms 138944 KB Output is correct
14 Correct 1110 ms 138928 KB Output is correct
15 Correct 9 ms 12908 KB Output is correct
16 Correct 10 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 12908 KB Output is correct
20 Correct 17 ms 13548 KB Output is correct
21 Correct 125 ms 18924 KB Output is correct
22 Correct 12 ms 13036 KB Output is correct
23 Correct 17 ms 13548 KB Output is correct
24 Correct 115 ms 18924 KB Output is correct
25 Correct 126 ms 18824 KB Output is correct
26 Correct 148 ms 19052 KB Output is correct
27 Correct 113 ms 19052 KB Output is correct
28 Correct 292 ms 27756 KB Output is correct
29 Correct 3675 ms 136960 KB Output is correct
30 Correct 286 ms 27884 KB Output is correct
31 Correct 3663 ms 137424 KB Output is correct
32 Correct 1797 ms 142008 KB Output is correct
33 Correct 1909 ms 142048 KB Output is correct
34 Correct 2952 ms 145144 KB Output is correct
35 Correct 9 ms 12908 KB Output is correct
36 Correct 10 ms 12908 KB Output is correct
37 Correct 116 ms 16876 KB Output is correct
38 Correct 1324 ms 132320 KB Output is correct
39 Correct 2142 ms 130528 KB Output is correct
40 Execution timed out 4077 ms 131296 KB Time limit exceeded
41 Halted 0 ms 0 KB -