oj.uz

Submission #355143

# Submission time Handle Problem Language Result Execution time Memory
355143 2021-01-22T09:29:14 Z ryansee Comparing Plants (IOI20_plants) C++14
30 / 100
 4000 ms 208656 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[18][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,17) 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,17,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 75628 KB Output is correct
2 Correct 45 ms 75532 KB Output is correct
3 Correct 45 ms 75628 KB Output is correct
4 Correct 45 ms 75628 KB Output is correct
5 Correct 45 ms 75628 KB Output is correct
6 Correct 130 ms 78444 KB Output is correct
7 Correct 350 ms 90056 KB Output is correct
8 Correct 2340 ms 197236 KB Output is correct
9 Correct 2425 ms 196156 KB Output is correct
10 Correct 2221 ms 196480 KB Output is correct
11 Correct 2040 ms 198320 KB Output is correct
12 Correct 1910 ms 202588 KB Output is correct
13 Correct 1606 ms 208656 KB Output is correct
14 Correct 1531 ms 208620 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 75628 KB Output is correct
2 Correct 45 ms 75628 KB Output is correct
3 Correct 45 ms 75608 KB Output is correct
4 Correct 45 ms 75628 KB Output is correct
5 Correct 47 ms 75628 KB Output is correct
6 Correct 60 ms 76268 KB Output is correct
7 Correct 155 ms 81516 KB Output is correct
8 Correct 47 ms 75756 KB Output is correct
9 Correct 56 ms 76268 KB Output is correct
10 Correct 154 ms 81516 KB Output is correct
11 Correct 139 ms 81644 KB Output is correct
12 Correct 140 ms 81900 KB Output is correct
13 Correct 154 ms 81516 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 75628 KB Output is correct
2 Correct 45 ms 75628 KB Output is correct
3 Correct 45 ms 75608 KB Output is correct
4 Correct 45 ms 75628 KB Output is correct
5 Correct 47 ms 75628 KB Output is correct
6 Correct 60 ms 76268 KB Output is correct
7 Correct 155 ms 81516 KB Output is correct
8 Correct 47 ms 75756 KB Output is correct
9 Correct 56 ms 76268 KB Output is correct
10 Correct 154 ms 81516 KB Output is correct
11 Correct 139 ms 81644 KB Output is correct
12 Correct 140 ms 81900 KB Output is correct
13 Correct 154 ms 81516 KB Output is correct
14 Correct 345 ms 90440 KB Output is correct
15 Execution timed out 4073 ms 199748 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 75628 KB Output is correct
2 Correct 46 ms 75628 KB Output is correct
3 Correct 167 ms 79596 KB Output is correct
4 Correct 2179 ms 203356 KB Output is correct
5 Correct 2834 ms 203100 KB Output is correct
6 Correct 3990 ms 202584 KB Output is correct
7 Execution timed out 4104 ms 203228 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 75628 KB Output is correct
2 Correct 45 ms 75668 KB Output is correct
3 Correct 50 ms 75628 KB Output is correct
4 Correct 45 ms 75628 KB Output is correct
5 Correct 45 ms 75628 KB Output is correct
6 Correct 47 ms 75756 KB Output is correct
7 Correct 70 ms 76396 KB Output is correct
8 Correct 64 ms 76396 KB Output is correct
9 Correct 70 ms 76396 KB Output is correct
10 Correct 65 ms 76396 KB Output is correct
11 Correct 70 ms 76396 KB Output is correct
12 Correct 68 ms 76396 KB Output is correct
13 Correct 60 ms 76396 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 75628 KB Output is correct
2 Correct 45 ms 75628 KB Output is correct
3 Correct 45 ms 75628 KB Output is correct
4 Correct 45 ms 75628 KB Output is correct
5 Correct 54 ms 76140 KB Output is correct
6 Correct 3628 ms 200944 KB Output is correct
7 Correct 3686 ms 201008 KB Output is correct
8 Execution timed out 4091 ms 200872 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 75628 KB Output is correct
2 Correct 45 ms 75532 KB Output is correct
3 Correct 45 ms 75628 KB Output is correct
4 Correct 45 ms 75628 KB Output is correct
5 Correct 45 ms 75628 KB Output is correct
6 Correct 130 ms 78444 KB Output is correct
7 Correct 350 ms 90056 KB Output is correct
8 Correct 2340 ms 197236 KB Output is correct
9 Correct 2425 ms 196156 KB Output is correct
10 Correct 2221 ms 196480 KB Output is correct
11 Correct 2040 ms 198320 KB Output is correct
12 Correct 1910 ms 202588 KB Output is correct
13 Correct 1606 ms 208656 KB Output is correct
14 Correct 1531 ms 208620 KB Output is correct
15 Correct 46 ms 75628 KB Output is correct
16 Correct 45 ms 75628 KB Output is correct
17 Correct 45 ms 75608 KB Output is correct
18 Correct 45 ms 75628 KB Output is correct
19 Correct 47 ms 75628 KB Output is correct
20 Correct 60 ms 76268 KB Output is correct
21 Correct 155 ms 81516 KB Output is correct
22 Correct 47 ms 75756 KB Output is correct
23 Correct 56 ms 76268 KB Output is correct
24 Correct 154 ms 81516 KB Output is correct
25 Correct 139 ms 81644 KB Output is correct
26 Correct 140 ms 81900 KB Output is correct
27 Correct 154 ms 81516 KB Output is correct
28 Correct 345 ms 90440 KB Output is correct
29 Execution timed out 4073 ms 199748 KB Time limit exceeded
30 Halted 0 ms 0 KB -