oj.uz

Submission #823164

# Submission time Handle Problem Language Result Execution time Memory
823164 2023-08-12T08:42:59 Z ymm Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 91628 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= l; --x)
typedef long long ll;
typedef std::pair<int,int> pii;
typedef std::pair<ll,ll> pll;
using namespace std;

const int N = 200'010;
const int lg = 20;
ll L[N][lg], R[N][lg];
int val[N], pos[N];
int n, k;

namespace seg1 {
	int a[2*N];
	void init() { fill(a, a+2*N, N); }

	void up(int p, int x) {
		p += N;
		while (p > 0) {
			a[p] = x;
			p /= 2;
		}
	}
	int get(int l, int r) {
		l += N;
		r += N;
		int ans = N;
		while (l < r) {
			if (l&1) ans = min(ans, a[l++]);
			if (r&1) ans = min(ans, a[--r]);
			l /= 2;
			r /= 2;
		}
		return ans;
	}
	int getc(int l, int r) {
		--r;
		l = (l%n+n)%n;
		r = (r%n+n)%n;
		++r;
		if (l >= r)
			return min(get(0, r), get(l, n));
		else
			return get(l, r);
	}
}

namespace seg2 {
	struct node {
		int mn;
		int lzy;
		int l, r;
		pii mxdif;
	} t[N*4];
	int sz;

	void merge(int i) {
		node &v = t[i], &l = t[2*i+1], &r = t[2*i+2];
		if (l.mn == r.mn) {
			v.mn = l.mn;
			v.l = l.l;
			v.r = r.r;
			v.mxdif = max(l.mxdif, r.mxdif);
			v.mxdif = max(v.mxdif, pii{r.l - l.r, r.l});
		} else {
			node &u = l.mn < r.mn? l: r;
			v = u;
			v.lzy = 0;
		}
	}
	void tag(int i, int x) { t[i].mn += x; t[i].lzy += x; }
	void ppg(int i) {
		if (t[i].lzy) {
			tag(2*i+1, t[i].lzy);
			tag(2*i+2, t[i].lzy);
			t[i].lzy = 0;
		}
	}

	void init(const vector<int> &vec, int i, int b, int e) {
		if (e-b == 1) {
			t[i].mn = vec[b];
			t[i].l = t[i].r = b;
			t[i].mxdif = {-1, -1};
			return;
		}
		init(vec, 2*i+1, b, (b+e)/2);
		init(vec, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void init(const vector<int> &vec) { sz = vec.size(); init(vec, 0, 0, sz); }

	void add(int l, int r, int x, int i, int b, int e) {
		if (l <= b && e <= r)
			return tag(i, x);
		if (r <= b || e <= l)
			return;
		ppg(i);
		add(l, r, x, 2*i+1, b, (b+e)/2);
		add(l, r, x, 2*i+2, (b+e)/2, e);
		merge(i);
	}
	void add(int l, int r, int x) { add(l, r, x, 0, 0, sz); }
	void addc(int l, int r, int x) {
		--r;
		l = (l%n+n)%n;
		r = (r%n+n)%n;
		++r;
		if (l >= r) {
			add(0, r, x);
			add(l, sz, x);
		} else {
			add(l, r, x);
		}
	}

	int get() {
		if (t[0].mxdif.first >= k)
			return t[0].mxdif.second;
		else
			return t[0].l;
	}
}

void init(int k, std::vector<int> r) {
	::k = k;
	n = r.size();
	seg2::init(r);
	LoopR (x,0,n) {
		int p = seg2::get();
		seg2::addc(p-k+1, p, -1);
		seg2::add(p, p+1, N);
		val[p] = x;
		pos[x] = p;
		//cerr << p << "-\n";
	}
	seg1::init();
	LoopR (i,0,n) {
		int l = seg1::getc(pos[i]-k+1, pos[i]);
		int r = seg1::getc(pos[i]+1, pos[i]+k);
		seg1::up(pos[i], i);
		L[pos[i]][0] = l == N? 0: (pos[i]-pos[l]+n)%n;
		R[pos[i]][0] = r == N? 0: (pos[r]-pos[i]+n)%n;
	}
	Loop (j,0,lg-1) {
		Loop (i,0,n) {
			int l = ((i - L[i][j])%n+n)%n;
			int r = ((i + R[i][j])%n+n)%n;
			L[i][j+1] = L[i][j] + L[l][j];
			R[i][j+1] = R[i][j] + R[r][j];
		}
	}
	//Loop (i,0,n)
	//	cerr << L[i][0] << ' ';
	//cerr << '\n';
	//Loop (i,0,n)
	//	cerr << R[i][0] << ' ';
	//cerr << '\n';
}

bool try_left(int x, int y)
{
	ll dis = 0;
	while (L[x][0]) {
		int x2 = ((x - L[x][0])%n+n)%n;
		if (val[x2] > val[y])
			break;
		dis += L[x][0];
		x = x2;
	}
	//LoopR (i,0,lg) {
	//	int x2 = ((x - L[x][i])%n+n)%n;
	//	if (val[x2] <= val[y]) {
	//		dis += L[x][i];
	//		x = x2;
	//	}
	//}
	return (x-y+n)%n <= dis;
}
bool try_right(int x, int y)
{
	ll dis = 0;
	while (R[x][0]) {
		int x2 = ((x + R[x][0])%n+n)%n;
		if (val[x2] > val[y])
			break;
		dis += R[x][0];
		x = x2;
	}
	//LoopR (i,0,lg) {
	//	int x2 = ((x + R[x][i])%n+n)%n;
	//	if (val[x2] <= val[y]) {
	//		dis += R[x][i];
	//		x = x2;
	//	}
	//}
	return (y-x+n)%n <= dis;
}
bool try_lr(int x, int y) { return try_left(x, y) || try_right(x, y); }

//int compare_plants(int x, int y) {
//	if (val[x] < val[y]) {
//		if (try_lr(x, y))
//			return -1;
//		else
//			return 0;
//	} else {
//		if (try_lr(y, x))
//			return 1;
//		else
//			return 0;
//	}
//}

bool vis[N];
bool dfs(int v, int dst)
{
	if (v == dst)
		return 1;
	vis[v] = 1;
	int l = ((v - L[v][0])%n+n)%n;
	int r = ((v + R[v][0])%n+n)%n;
	for (int u : {l, r}) {
		if (!vis[u] && dfs(u, dst))
			return 1;
	}
	return 0;
}

int compare_plants(int x, int y) {
	//if (val[x] > val[y])
	//	return 1;
	//else
	//	return -1;
	memset(vis, 0, n);
	if (dfs(x, y))
		return -1;
	memset(vis, 0, n);
	if (dfs(y, x))
		return 1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20564 KB Output is correct
2 Correct 9 ms 20632 KB Output is correct
3 Correct 8 ms 20564 KB Output is correct
4 Correct 8 ms 20564 KB Output is correct
5 Correct 8 ms 20564 KB Output is correct
6 Correct 59 ms 23488 KB Output is correct
7 Correct 788 ms 30576 KB Output is correct
8 Correct 1156 ms 89280 KB Output is correct
9 Correct 1833 ms 91628 KB Output is correct
10 Execution timed out 4090 ms 91588 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 9 ms 20612 KB Output is correct
3 Correct 8 ms 20564 KB Output is correct
4 Correct 10 ms 20676 KB Output is correct
5 Correct 9 ms 20692 KB Output is correct
6 Correct 56 ms 21080 KB Output is correct
7 Execution timed out 4070 ms 24928 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 20564 KB Output is correct
2 Correct 9 ms 20612 KB Output is correct
3 Correct 8 ms 20564 KB Output is correct
4 Correct 10 ms 20676 KB Output is correct
5 Correct 9 ms 20692 KB Output is correct
6 Correct 56 ms 21080 KB Output is correct
7 Execution timed out 4070 ms 24928 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 20564 KB Output is correct
2 Correct 9 ms 20564 KB Output is correct
3 Correct 2815 ms 24352 KB Output is correct
4 Execution timed out 4014 ms 90760 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 20624 KB Output is correct
2 Correct 10 ms 20564 KB Output is correct
3 Correct 8 ms 20616 KB Output is correct
4 Correct 8 ms 20564 KB Output is correct
5 Correct 9 ms 20692 KB Output is correct
6 Correct 12 ms 20820 KB Output is correct
7 Correct 65 ms 21572 KB Output is correct
8 Correct 145 ms 21544 KB Output is correct
9 Correct 135 ms 21548 KB Output is correct
10 Correct 141 ms 21548 KB Output is correct
11 Correct 89 ms 21580 KB Output is correct
12 Correct 140 ms 21548 KB Output is correct
13 Correct 150 ms 21624 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20624 KB Output is correct
2 Correct 9 ms 20600 KB Output is correct
3 Correct 8 ms 20684 KB Output is correct
4 Correct 7 ms 20692 KB Output is correct
5 Correct 25 ms 20948 KB Output is correct
6 Execution timed out 4021 ms 89280 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 20564 KB Output is correct
2 Correct 9 ms 20632 KB Output is correct
3 Correct 8 ms 20564 KB Output is correct
4 Correct 8 ms 20564 KB Output is correct
5 Correct 8 ms 20564 KB Output is correct
6 Correct 59 ms 23488 KB Output is correct
7 Correct 788 ms 30576 KB Output is correct
8 Correct 1156 ms 89280 KB Output is correct
9 Correct 1833 ms 91628 KB Output is correct
10 Execution timed out 4090 ms 91588 KB Time limit exceeded
11 Halted 0 ms 0 KB -