oj.uz

Submission #355131

# Submission time Handle Problem Language Result Execution time Memory
355131 2021-01-22T09:22:12 Z ryansee Comparing Plants (IOI20_plants) C++14
30 / 100
 4000 ms 212700 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=int; 
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*2];
inline int cy(ll x) {
	if(x < 0) x += n;
	if(x >= n) x -= n;
	return x;
}
int 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(INF, 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(INF, 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;
	pi v;
	node2*l,*r;
	node2(int S,int E){
		s=S,e=E,m=(s+e)>>1;
		v = pi(-INF, -1);
		if(s^e)l=new node2(s,m),r=new node2(m+1,e);
	}
	pi 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 max(l->rmq(x, m), r->rmq(m+1, y));
	}
	void set(int x) {
		if(s==e) {
			v = pi(A[s], s);
			return;
		}
		if(x>m) r->set(x);
		else l->set(x);
		v = max(l->v, r->v);
	}
} *seg2;
struct tree {
	int p[19][MAXN*2];
	bitset<MAXN*2> r;
	vector<int> v[MAXN*2];
	tree() {
		mmst(p, 0), r.set();
	}
	void add(int x,int y) {
		if(y==-1||x==y) return;
		r[x]=0, v[y].eb(x);
	}
	void solve() {
		function<void(ll)>dfs=[&](int x) {
			for(auto i:v[x]) p[0][i]=x, dfs(i);
		};
		FOR(i,0,2*n-1) if(r[i]) p[0][i]=2*n, dfs(i);
		FOR(j,1,18) FOR(i,0,2*n-1) if(p[j-1][i]==2*n) p[j][i]=2*n; else p[j][i]=p[j-1][p[j-1][i]];
	}
	inline int h(int x,int l) {
		DEC(i,18,0) if(p[i][x] < l) x = p[i][x];
		return p[0][x];
	}
} 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));
	}
	vector<int> p;
	FOR(i,0,n-1) p.eb(i), p.eb(i+n), A[i+n]=A[i];
	sort(all(p), [](int x,int y){return A[x]<A[y];});
	seg2=new node2(0, 2*n-1);
	for(auto i:p) {
		int target = seg2->rmq(i, min(2*n-1, i+k-1)).s; // connect to shortest tower within k that is taller than you
		t[0].add(i, target);
		seg2->set(i);
	}
	reverse(all(p));
	seg2=new node2(0, 2*n-1);
	for(auto i:p) {
		int target = seg2->rmq(i, min(2*n-1, i+k-1)).s;
		t[1].add(i, target);
		A[i]=-A[i], seg2->set(i), A[i]=-A[i];
	}
	FOR(i,0,1) t[i].solve();
}
int compare_plants(int x, int y) {
	if(dist(x, y) < k) {
		return A[x] < A[y] ? 1 : -1;
	}
	int i = t[0].h(x, y);
	if(i <= y+k-1 && A[y] <= A[i]) {
		return -1;
	}
	i = t[1].h(x, y);
	if(i <= y+k-1 && A[y] >= A[i]) {
		return 1;
	}
	swap(x, y);
	y += n;
	i = t[0].h(x, y);
	if(i <= min(2*n-1, y+k-1) && A[y] <= A[i]) {
		return 1;
	}
	i = t[1].h(x, y);
	if(i <= min(2*n-1, y+k-1) && A[y] >= A[i]) {
		return -1;
	}
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78700 KB Output is correct
2 Correct 43 ms 78700 KB Output is correct
3 Correct 45 ms 78700 KB Output is correct
4 Correct 43 ms 78700 KB Output is correct
5 Correct 45 ms 78700 KB Output is correct
6 Correct 126 ms 81504 KB Output is correct
7 Correct 363 ms 93256 KB Output is correct
8 Correct 2401 ms 199280 KB Output is correct
9 Correct 2658 ms 200316 KB Output is correct
10 Correct 2294 ms 200708 KB Output is correct
11 Correct 2081 ms 202472 KB Output is correct
12 Correct 1960 ms 206684 KB Output is correct
13 Correct 1604 ms 212700 KB Output is correct
14 Correct 1543 ms 212700 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 78700 KB Output is correct
2 Correct 48 ms 78700 KB Output is correct
3 Correct 47 ms 78700 KB Output is correct
4 Correct 48 ms 78700 KB Output is correct
5 Correct 50 ms 78828 KB Output is correct
6 Correct 55 ms 79468 KB Output is correct
7 Correct 155 ms 85612 KB Output is correct
8 Correct 50 ms 78828 KB Output is correct
9 Correct 57 ms 79468 KB Output is correct
10 Correct 155 ms 85740 KB Output is correct
11 Correct 138 ms 85764 KB Output is correct
12 Correct 161 ms 85996 KB Output is correct
13 Correct 156 ms 85740 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 78700 KB Output is correct
2 Correct 48 ms 78700 KB Output is correct
3 Correct 47 ms 78700 KB Output is correct
4 Correct 48 ms 78700 KB Output is correct
5 Correct 50 ms 78828 KB Output is correct
6 Correct 55 ms 79468 KB Output is correct
7 Correct 155 ms 85612 KB Output is correct
8 Correct 50 ms 78828 KB Output is correct
9 Correct 57 ms 79468 KB Output is correct
10 Correct 155 ms 85740 KB Output is correct
11 Correct 138 ms 85764 KB Output is correct
12 Correct 161 ms 85996 KB Output is correct
13 Correct 156 ms 85740 KB Output is correct
14 Correct 390 ms 94680 KB Output is correct
15 Execution timed out 4048 ms 203740 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 78700 KB Output is correct
2 Correct 47 ms 78700 KB Output is correct
3 Correct 179 ms 83948 KB Output is correct
4 Correct 2217 ms 207636 KB Output is correct
5 Correct 2886 ms 207320 KB Output is correct
6 Execution timed out 4013 ms 206832 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 78700 KB Output is correct
2 Correct 47 ms 78700 KB Output is correct
3 Correct 48 ms 78700 KB Output is correct
4 Correct 47 ms 78700 KB Output is correct
5 Correct 48 ms 78700 KB Output is correct
6 Correct 49 ms 78828 KB Output is correct
7 Correct 77 ms 79980 KB Output is correct
8 Correct 64 ms 79852 KB Output is correct
9 Correct 73 ms 79852 KB Output is correct
10 Correct 66 ms 79852 KB Output is correct
11 Correct 74 ms 79852 KB Output is correct
12 Correct 77 ms 79852 KB Output is correct
13 Correct 67 ms 79852 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 78884 KB Output is correct
2 Correct 46 ms 78700 KB Output is correct
3 Correct 47 ms 78700 KB Output is correct
4 Correct 47 ms 78700 KB Output is correct
5 Correct 54 ms 79596 KB Output is correct
6 Correct 3548 ms 205032 KB Output is correct
7 Correct 3701 ms 205104 KB Output is correct
8 Execution timed out 4062 ms 205084 KB Time limit exceeded
9 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78700 KB Output is correct
2 Correct 43 ms 78700 KB Output is correct
3 Correct 45 ms 78700 KB Output is correct
4 Correct 43 ms 78700 KB Output is correct
5 Correct 45 ms 78700 KB Output is correct
6 Correct 126 ms 81504 KB Output is correct
7 Correct 363 ms 93256 KB Output is correct
8 Correct 2401 ms 199280 KB Output is correct
9 Correct 2658 ms 200316 KB Output is correct
10 Correct 2294 ms 200708 KB Output is correct
11 Correct 2081 ms 202472 KB Output is correct
12 Correct 1960 ms 206684 KB Output is correct
13 Correct 1604 ms 212700 KB Output is correct
14 Correct 1543 ms 212700 KB Output is correct
15 Correct 47 ms 78700 KB Output is correct
16 Correct 48 ms 78700 KB Output is correct
17 Correct 47 ms 78700 KB Output is correct
18 Correct 48 ms 78700 KB Output is correct
19 Correct 50 ms 78828 KB Output is correct
20 Correct 55 ms 79468 KB Output is correct
21 Correct 155 ms 85612 KB Output is correct
22 Correct 50 ms 78828 KB Output is correct
23 Correct 57 ms 79468 KB Output is correct
24 Correct 155 ms 85740 KB Output is correct
25 Correct 138 ms 85764 KB Output is correct
26 Correct 161 ms 85996 KB Output is correct
27 Correct 156 ms 85740 KB Output is correct
28 Correct 390 ms 94680 KB Output is correct
29 Execution timed out 4048 ms 203740 KB Time limit exceeded
30 Halted 0 ms 0 KB -