oj.uz

Submission #354299

# Submission time Handle Problem Language Result Execution time Memory
354299 2021-01-21T17:03:43 Z ryansee Comparing Plants (IOI20_plants) C++14
55 / 100
 2739 ms 48108 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;
}
vector<int> v[306];
bitset<306> reach[306];
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));
}
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 = -1;
		// FOR(i,0,n-1) if(!gone[i] && r[i] == 0) {
			// DEC(jj,i-1,i-k+1) {
				// int j = (jj + n) % n;
				// if(!gone[j] && r[j] == 0) goto no;
			// }
			// start = i;
			// break;
			// no:;
		// }
		start = seg->rmq(0, n-1).s.s;
		if(start == -1) break;
		// gone[start] = 1;
		seg->set(start);
		// FOR(i,start+1,start+k-1) if(!gone[i%n]) {
			// A[i%n]=max(A[i%n], A[start]+1);
		// }
		update(start+1, start+k-1, pi(A[start]+1, 2));
		update(start+1, start+k-1, pi(-1, 1));
		// FOR(i,start-k+1,start-1) if(!gone[(i+n)%n]) {
			// A[(i+n)%n] = max(A[(i+n)%n], A[start]+1), -- r[(i+n)%n];
		// }
		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));
	}
	// FOR(i,0,n-1) assert(r[i]==0);
	
	if(n <= 300) {
		FOR(i,0,n-1) {
			FOR(jj,i+1,i+k-1) { int j=cy(jj);
				if(A[i] > A[j]) {
					v[i].eb(j);
				} else {
					v[j].eb(i);
				}
			}
		}
		function<void(ll,ll)>dfs=[&](ll x,ll o){
			if(reach[o][x]) return;
			reach[o][x]=1;
			for(auto i:v[x]) dfs(i, o);
		};
		FOR(i,0,n-1) dfs(i, i);
	}
}
int compare_plants(int x, int y) {
	if(n > 300 || reach[x][y] || reach[y][x]) return A[x] < A[y] ? 1 : -1;
	else return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 61 ms 3180 KB Output is correct
7 Incorrect 129 ms 7404 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 368 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 7 ms 620 KB Output is correct
7 Correct 96 ms 4204 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 7 ms 620 KB Output is correct
10 Correct 96 ms 4296 KB Output is correct
11 Correct 90 ms 4332 KB Output is correct
12 Correct 86 ms 4332 KB Output is correct
13 Correct 101 ms 4204 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 368 KB Output is correct
5 Correct 3 ms 364 KB Output is correct
6 Correct 7 ms 620 KB Output is correct
7 Correct 96 ms 4204 KB Output is correct
8 Correct 4 ms 492 KB Output is correct
9 Correct 7 ms 620 KB Output is correct
10 Correct 96 ms 4296 KB Output is correct
11 Correct 90 ms 4332 KB Output is correct
12 Correct 86 ms 4332 KB Output is correct
13 Correct 101 ms 4204 KB Output is correct
14 Correct 238 ms 7532 KB Output is correct
15 Correct 2693 ms 47980 KB Output is correct
16 Correct 241 ms 9580 KB Output is correct
17 Correct 2675 ms 47980 KB Output is correct
18 Correct 1456 ms 47596 KB Output is correct
19 Correct 1589 ms 48108 KB Output is correct
20 Correct 2113 ms 48108 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 69 ms 3564 KB Output is correct
4 Correct 1054 ms 44268 KB Output is correct
5 Correct 1397 ms 47440 KB Output is correct
6 Correct 1976 ms 47528 KB Output is correct
7 Correct 2495 ms 47728 KB Output is correct
8 Correct 2739 ms 47980 KB Output is correct
9 Correct 1180 ms 47340 KB Output is correct
10 Correct 1252 ms 47340 KB Output is correct
11 Correct 694 ms 47084 KB Output is correct
12 Correct 1210 ms 47596 KB Output is correct
13 Correct 1449 ms 47596 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 2 ms 492 KB Output is correct
7 Correct 15 ms 1004 KB Output is correct
8 Correct 36 ms 1260 KB Output is correct
9 Correct 17 ms 1004 KB Output is correct
10 Correct 38 ms 1260 KB Output is correct
11 Correct 16 ms 1004 KB Output is correct
12 Correct 18 ms 1132 KB Output is correct
13 Correct 74 ms 1644 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Incorrect 6 ms 492 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 61 ms 3180 KB Output is correct
7 Incorrect 129 ms 7404 KB Output isn't correct
8 Halted 0 ms 0 KB -