oj.uz

Submission #354965

# Submission time Handle Problem Language Result Execution time Memory
354965 2021-01-22T07:44:24 Z ryansee Comparing Plants (IOI20_plants) C++14
32 / 100
 2964 ms 109932 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;
		if(s^e)l=new node2(s,m),r=new node2(m+1,e),v=comb(l->v,r->v);
		else v={pi(A[s], s), pi(A[s], s)};
	}
	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;
	}
} *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(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);
	} */
	
	seg2=new node2(0, n-1);
	FOR(i,0,n-1) {
		int target = seg2->mi(i, i+k-1);
		t[0].add(i, target);
	}
	FOR(i,0,n-1) {
		int target = seg2->mx(i, i+k-1);
		t[1].add(i, target);
	}
	// 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

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13164 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 74 ms 16748 KB Output is correct
7 Correct 153 ms 25836 KB Output is correct
8 Correct 944 ms 97388 KB Output is correct
9 Correct 921 ms 97260 KB Output is correct
10 Correct 903 ms 97608 KB Output is correct
11 Correct 908 ms 99488 KB Output is correct
12 Correct 893 ms 103788 KB Output is correct
13 Correct 795 ms 109932 KB Output is correct
14 Correct 1008 ms 109888 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 9 ms 12908 KB Output is correct
3 Correct 11 ms 12908 KB Output is correct
4 Correct 11 ms 12908 KB Output is correct
5 Correct 13 ms 12908 KB Output is correct
6 Correct 17 ms 13420 KB Output is correct
7 Correct 114 ms 19564 KB Output is correct
8 Correct 11 ms 13036 KB Output is correct
9 Correct 18 ms 13420 KB Output is correct
10 Correct 113 ms 19564 KB Output is correct
11 Correct 100 ms 19564 KB Output is correct
12 Correct 100 ms 19692 KB Output is correct
13 Correct 124 ms 19564 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 9 ms 12908 KB Output is correct
3 Correct 11 ms 12908 KB Output is correct
4 Correct 11 ms 12908 KB Output is correct
5 Correct 13 ms 12908 KB Output is correct
6 Correct 17 ms 13420 KB Output is correct
7 Correct 114 ms 19564 KB Output is correct
8 Correct 11 ms 13036 KB Output is correct
9 Correct 18 ms 13420 KB Output is correct
10 Correct 113 ms 19564 KB Output is correct
11 Correct 100 ms 19564 KB Output is correct
12 Correct 100 ms 19692 KB Output is correct
13 Correct 124 ms 19564 KB Output is correct
14 Correct 276 ms 25452 KB Output is correct
15 Correct 2911 ms 93924 KB Output is correct
16 Correct 303 ms 25592 KB Output is correct
17 Correct 2964 ms 93672 KB Output is correct
18 Correct 1675 ms 95768 KB Output is correct
19 Correct 1772 ms 96380 KB Output is correct
20 Correct 2318 ms 94116 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 9 ms 12908 KB Output is correct
3 Incorrect 81 ms 18156 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 12908 KB Output is correct
2 Correct 10 ms 13036 KB Output is correct
3 Correct 9 ms 12908 KB Output is correct
4 Correct 9 ms 12908 KB Output is correct
5 Incorrect 9 ms 12908 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 9 ms 12908 KB Output is correct
4 Incorrect 11 ms 12908 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 13164 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 74 ms 16748 KB Output is correct
7 Correct 153 ms 25836 KB Output is correct
8 Correct 944 ms 97388 KB Output is correct
9 Correct 921 ms 97260 KB Output is correct
10 Correct 903 ms 97608 KB Output is correct
11 Correct 908 ms 99488 KB Output is correct
12 Correct 893 ms 103788 KB Output is correct
13 Correct 795 ms 109932 KB Output is correct
14 Correct 1008 ms 109888 KB Output is correct
15 Correct 9 ms 12908 KB Output is correct
16 Correct 9 ms 12908 KB Output is correct
17 Correct 11 ms 12908 KB Output is correct
18 Correct 11 ms 12908 KB Output is correct
19 Correct 13 ms 12908 KB Output is correct
20 Correct 17 ms 13420 KB Output is correct
21 Correct 114 ms 19564 KB Output is correct
22 Correct 11 ms 13036 KB Output is correct
23 Correct 18 ms 13420 KB Output is correct
24 Correct 113 ms 19564 KB Output is correct
25 Correct 100 ms 19564 KB Output is correct
26 Correct 100 ms 19692 KB Output is correct
27 Correct 124 ms 19564 KB Output is correct
28 Correct 276 ms 25452 KB Output is correct
29 Correct 2911 ms 93924 KB Output is correct
30 Correct 303 ms 25592 KB Output is correct
31 Correct 2964 ms 93672 KB Output is correct
32 Correct 1675 ms 95768 KB Output is correct
33 Correct 1772 ms 96380 KB Output is correct
34 Correct 2318 ms 94116 KB Output is correct
35 Correct 9 ms 12908 KB Output is correct
36 Correct 9 ms 12908 KB Output is correct
37 Incorrect 81 ms 18156 KB Output isn't correct
38 Halted 0 ms 0 KB -