oj.uz

Submission #823112

# Submission time Handle Problem Language Result Execution time Memory
823112 2023-08-12T08:12:34 Z ymm Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 42056 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;
vector<int> A[N];
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;
	}
	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);
		if (l != N)
			A[pos[i]].push_back(pos[l]);
		if (r != N)
			A[pos[i]].push_back(pos[r]);
		seg1::up(pos[i], i);
	}
}

bool vis[N];
bool dfs(int v, int dst)
{
	if (v == dst)
		return 1;
	vis[v] = 1;
	for (int u : A[v]) {
		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 11 ms 25300 KB Output is correct
2 Correct 11 ms 25300 KB Output is correct
3 Correct 13 ms 25340 KB Output is correct
4 Correct 12 ms 25336 KB Output is correct
5 Correct 14 ms 25300 KB Output is correct
6 Correct 64 ms 29088 KB Output is correct
7 Correct 369 ms 30584 KB Output is correct
8 Correct 1054 ms 38196 KB Output is correct
9 Correct 1305 ms 39948 KB Output is correct
10 Correct 3014 ms 40048 KB Output is correct
11 Execution timed out 4043 ms 40940 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25288 KB Output is correct
2 Correct 11 ms 25308 KB Output is correct
3 Correct 11 ms 25332 KB Output is correct
4 Correct 12 ms 25252 KB Output is correct
5 Correct 12 ms 25328 KB Output is correct
6 Correct 32 ms 25528 KB Output is correct
7 Execution timed out 4046 ms 30004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25288 KB Output is correct
2 Correct 11 ms 25308 KB Output is correct
3 Correct 11 ms 25332 KB Output is correct
4 Correct 12 ms 25252 KB Output is correct
5 Correct 12 ms 25328 KB Output is correct
6 Correct 32 ms 25528 KB Output is correct
7 Execution timed out 4046 ms 30004 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 10 ms 25332 KB Output is correct
3 Correct 996 ms 29956 KB Output is correct
4 Execution timed out 4030 ms 42056 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25364 KB Output is correct
2 Correct 11 ms 25300 KB Output is correct
3 Correct 11 ms 25328 KB Output is correct
4 Correct 13 ms 25308 KB Output is correct
5 Correct 11 ms 25300 KB Output is correct
6 Correct 13 ms 25344 KB Output is correct
7 Correct 35 ms 26232 KB Output is correct
8 Correct 65 ms 26236 KB Output is correct
9 Correct 57 ms 26212 KB Output is correct
10 Correct 64 ms 26224 KB Output is correct
11 Correct 46 ms 26232 KB Output is correct
12 Correct 61 ms 26304 KB Output is correct
13 Correct 62 ms 26240 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25332 KB Output is correct
2 Correct 12 ms 25300 KB Output is correct
3 Correct 11 ms 25328 KB Output is correct
4 Correct 11 ms 25300 KB Output is correct
5 Correct 17 ms 25336 KB Output is correct
6 Execution timed out 4041 ms 38476 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 11 ms 25300 KB Output is correct
3 Correct 13 ms 25340 KB Output is correct
4 Correct 12 ms 25336 KB Output is correct
5 Correct 14 ms 25300 KB Output is correct
6 Correct 64 ms 29088 KB Output is correct
7 Correct 369 ms 30584 KB Output is correct
8 Correct 1054 ms 38196 KB Output is correct
9 Correct 1305 ms 39948 KB Output is correct
10 Correct 3014 ms 40048 KB Output is correct
11 Execution timed out 4043 ms 40940 KB Time limit exceeded
12 Halted 0 ms 0 KB -