oj.uz

Submission #355194

# Submission time Handle Problem Language Result Execution time Memory
355194 2021-01-22T09:56:13 Z ryansee Comparing Plants (IOI20_plants) C++14
100 / 100
 3677 ms 165084 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,pi nval2=pi(0, 0)) {
		if(s==x&&e==y) {
			if(nval.s <= 1) lazy[nval.s] += nval.f;
			else lazy[nval.s] = max(lazy[nval.s], nval.f);
			if(nval2.s <= 1) lazy[nval2.s] += nval2.f;
			else lazy[nval2.s] = max(lazy[nval2.s], nval2.f);
			return;
		}
		if(x>m) r->update(x,y,nval,nval2);
		else if(y<=m) l->update(x,y,nval,nval2);
		else l->update(x,m,nval,nval2),r->update(m+1,y,nval,nval2);
		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) {
		A[x] = max(A[x], lazy[2]);
		if(s==e) {
			v = spi(INF, pi(0, -1));
			return;
		}
		if(x>m) r->set(x);
		else l->set(x);
		v = min(l->v, r->v);
	}
} *seg;
void update(int x,int y,pi nval,pi nval2=pi(0,0)) {
	x=cy(x), y=cy(y);
	if(x<=y) seg->update(x,y,nval,nval2);
	else seg->update(x,n-1,nval,nval2), seg->update(0,y,nval,nval2);
}
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];
	void init() {
		FOR(i,0,2*n-1) p[0][i] = 2*n;
	}
	void add(int x,int y) {
		if(y==-1||x==y) return;
		p[0][x] = y;
	}
	void solve() {
		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(), t[0].init(), t[1].init();
	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), pi(-1, 1));
		update(start-k+1, start-1, pi(A[start]+1, 2), 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 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 83 ms 3436 KB Output is correct
7 Correct 288 ms 19400 KB Output is correct
8 Correct 1864 ms 164956 KB Output is correct
9 Correct 1960 ms 164828 KB Output is correct
10 Correct 1815 ms 164828 KB Output is correct
11 Correct 1690 ms 164828 KB Output is correct
12 Correct 1626 ms 164976 KB Output is correct
13 Correct 1294 ms 164956 KB Output is correct
14 Correct 1260 ms 165084 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 8 ms 1516 KB Output is correct
7 Correct 103 ms 7532 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct
10 Correct 98 ms 7532 KB Output is correct
11 Correct 94 ms 7368 KB Output is correct
12 Correct 89 ms 7660 KB Output is correct
13 Correct 96 ms 7532 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 8 ms 1516 KB Output is correct
7 Correct 103 ms 7532 KB Output is correct
8 Correct 3 ms 748 KB Output is correct
9 Correct 8 ms 1516 KB Output is correct
10 Correct 98 ms 7532 KB Output is correct
11 Correct 94 ms 7368 KB Output is correct
12 Correct 89 ms 7660 KB Output is correct
13 Correct 96 ms 7532 KB Output is correct
14 Correct 246 ms 19528 KB Output is correct
15 Correct 3257 ms 164700 KB Output is correct
16 Correct 244 ms 19528 KB Output is correct
17 Correct 3266 ms 164932 KB Output is correct
18 Correct 1442 ms 164700 KB Output is correct
19 Correct 1542 ms 164752 KB Output is correct
20 Correct 2618 ms 164756 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 122 ms 4992 KB Output is correct
4 Correct 1784 ms 164700 KB Output is correct
5 Correct 2269 ms 164844 KB Output is correct
6 Correct 3203 ms 164756 KB Output is correct
7 Correct 3677 ms 164752 KB Output is correct
8 Correct 3455 ms 164828 KB Output is correct
9 Correct 1941 ms 164948 KB Output is correct
10 Correct 1796 ms 164756 KB Output is correct
11 Correct 1271 ms 164824 KB Output is correct
12 Correct 1446 ms 164828 KB Output is correct
13 Correct 1600 ms 164872 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 3 ms 748 KB Output is correct
7 Correct 27 ms 1516 KB Output is correct
8 Correct 18 ms 1516 KB Output is correct
9 Correct 25 ms 1388 KB Output is correct
10 Correct 18 ms 1516 KB Output is correct
11 Correct 27 ms 1516 KB Output is correct
12 Correct 25 ms 1516 KB Output is correct
13 Correct 18 ms 1536 KB Output is correct

Subtask #6
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 7 ms 1388 KB Output is correct
6 Correct 2810 ms 164788 KB Output is correct
7 Correct 2985 ms 164744 KB Output is correct
8 Correct 3208 ms 164776 KB Output is correct
9 Correct 3294 ms 164744 KB Output is correct
10 Correct 1890 ms 164700 KB Output is correct
11 Correct 2134 ms 164776 KB Output is correct
12 Correct 1563 ms 164828 KB Output is correct
13 Correct 2237 ms 165000 KB Output is correct
14 Correct 2831 ms 164744 KB Output is correct
15 Correct 3184 ms 164752 KB Output is correct
16 Correct 1497 ms 164788 KB Output is correct
17 Correct 1896 ms 164724 KB Output is correct

Subtask #7
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 620 KB Output is correct
2 Correct 1 ms 620 KB Output is correct
3 Correct 1 ms 620 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 83 ms 3436 KB Output is correct
7 Correct 288 ms 19400 KB Output is correct
8 Correct 1864 ms 164956 KB Output is correct
9 Correct 1960 ms 164828 KB Output is correct
10 Correct 1815 ms 164828 KB Output is correct
11 Correct 1690 ms 164828 KB Output is correct
12 Correct 1626 ms 164976 KB Output is correct
13 Correct 1294 ms 164956 KB Output is correct
14 Correct 1260 ms 165084 KB Output is correct
15 Correct 1 ms 620 KB Output is correct
16 Correct 1 ms 620 KB Output is correct
17 Correct 1 ms 620 KB Output is correct
18 Correct 1 ms 620 KB Output is correct
19 Correct 1 ms 620 KB Output is correct
20 Correct 8 ms 1516 KB Output is correct
21 Correct 103 ms 7532 KB Output is correct
22 Correct 3 ms 748 KB Output is correct
23 Correct 8 ms 1516 KB Output is correct
24 Correct 98 ms 7532 KB Output is correct
25 Correct 94 ms 7368 KB Output is correct
26 Correct 89 ms 7660 KB Output is correct
27 Correct 96 ms 7532 KB Output is correct
28 Correct 246 ms 19528 KB Output is correct
29 Correct 3257 ms 164700 KB Output is correct
30 Correct 244 ms 19528 KB Output is correct
31 Correct 3266 ms 164932 KB Output is correct
32 Correct 1442 ms 164700 KB Output is correct
33 Correct 1542 ms 164752 KB Output is correct
34 Correct 2618 ms 164756 KB Output is correct
35 Correct 1 ms 620 KB Output is correct
36 Correct 1 ms 620 KB Output is correct
37 Correct 122 ms 4992 KB Output is correct
38 Correct 1784 ms 164700 KB Output is correct
39 Correct 2269 ms 164844 KB Output is correct
40 Correct 3203 ms 164756 KB Output is correct
41 Correct 3677 ms 164752 KB Output is correct
42 Correct 3455 ms 164828 KB Output is correct
43 Correct 1941 ms 164948 KB Output is correct
44 Correct 1796 ms 164756 KB Output is correct
45 Correct 1271 ms 164824 KB Output is correct
46 Correct 1446 ms 164828 KB Output is correct
47 Correct 1600 ms 164872 KB Output is correct
48 Correct 1 ms 620 KB Output is correct
49 Correct 1 ms 620 KB Output is correct
50 Correct 1 ms 620 KB Output is correct
51 Correct 1 ms 620 KB Output is correct
52 Correct 1 ms 620 KB Output is correct
53 Correct 3 ms 748 KB Output is correct
54 Correct 27 ms 1516 KB Output is correct
55 Correct 18 ms 1516 KB Output is correct
56 Correct 25 ms 1388 KB Output is correct
57 Correct 18 ms 1516 KB Output is correct
58 Correct 27 ms 1516 KB Output is correct
59 Correct 25 ms 1516 KB Output is correct
60 Correct 18 ms 1536 KB Output is correct
61 Correct 151 ms 4972 KB Output is correct
62 Correct 328 ms 19528 KB Output is correct
63 Correct 2536 ms 164700 KB Output is correct
64 Correct 3177 ms 164776 KB Output is correct
65 Correct 3388 ms 164744 KB Output is correct
66 Correct 3629 ms 164744 KB Output is correct
67 Correct 3429 ms 164744 KB Output is correct
68 Correct 2199 ms 164908 KB Output is correct
69 Correct 2268 ms 164784 KB Output is correct
70 Correct 1891 ms 164700 KB Output is correct
71 Correct 2459 ms 164828 KB Output is correct
72 Correct 3385 ms 164744 KB Output is correct
73 Correct 3659 ms 164776 KB Output is correct
74 Correct 2725 ms 164700 KB Output is correct
75 Correct 1918 ms 164744 KB Output is correct