oj.uz

Submission #354338

# Submission time Handle Problem Language Result Execution time Memory
354338 2021-01-21T18:38:29 Z ryansee Comparing Plants (IOI20_plants) C++14
25 / 100
 4000 ms 48016 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];
int dp[2][MAXN], dp2[2][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);
	}
	dp[0][0]=dp[1][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];
		}
	}
	dp2[0][0]=dp2[1][0]=1;
	DEC(ii,0,-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 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;
}

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 65 ms 3180 KB Output is correct
7 Incorrect 130 ms 7788 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 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 3 ms 492 KB Output is correct
6 Correct 26 ms 620 KB Output is correct
7 Correct 606 ms 4372 KB Output is correct
8 Correct 5 ms 492 KB Output is correct
9 Correct 26 ms 620 KB Output is correct
10 Correct 578 ms 4332 KB Output is correct
11 Correct 349 ms 4332 KB Output is correct
12 Correct 352 ms 4460 KB Output is correct
13 Correct 724 ms 4576 KB Output is correct

Subtask #3
0 / 13.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 3 ms 492 KB Output is correct
6 Correct 26 ms 620 KB Output is correct
7 Correct 606 ms 4372 KB Output is correct
8 Correct 5 ms 492 KB Output is correct
9 Correct 26 ms 620 KB Output is correct
10 Correct 578 ms 4332 KB Output is correct
11 Correct 349 ms 4332 KB Output is correct
12 Correct 352 ms 4460 KB Output is correct
13 Correct 724 ms 4576 KB Output is correct
14 Execution timed out 4043 ms 7312 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 500 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 71 ms 3692 KB Output is correct
4 Correct 1068 ms 47468 KB Output is correct
5 Correct 1886 ms 47404 KB Output is correct
6 Execution timed out 4018 ms 45748 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 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 16 ms 1132 KB Output is correct
8 Correct 43 ms 1260 KB Output is correct
9 Correct 20 ms 1132 KB Output is correct
10 Correct 36 ms 1260 KB Output is correct
11 Correct 16 ms 1132 KB Output is correct
12 Correct 18 ms 1132 KB Output is correct
13 Correct 76 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 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 9 ms 620 KB Output is correct
6 Correct 1904 ms 47440 KB Output is correct
7 Execution timed out 4064 ms 48016 KB Time limit exceeded
8 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 65 ms 3180 KB Output is correct
7 Incorrect 130 ms 7788 KB Output isn't correct
8 Halted 0 ms 0 KB -