oj.uz

Submission #809408

# Submission time Handle Problem Language Result Execution time Memory
809408 2023-08-06T01:24:49 Z LittleCube Comparing Plants (IOI20_plants) C++17
25 / 100
 1484 ms 102584 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
using namespace std;

int n, state[800005], order[200005], out[200005], in[200005];
bitset<20000> reachability[20000];

struct segTree
{
	pll seg[800005];
	ll lazy[800005];

	void init(int i = 1, int L = 0, int R = n - 1)
	{
		seg[i].S = L;
		if (L == R)
			return;
		int mid = (L + R) / 2;
		init(i << 1, L, mid);
		init(i << 1 | 1, mid + 1, R);
	}

	void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = n - 1)
	{
		if (mL <= L && R <= mR)
		{
			lazy[i] += val;
			seg[i].F += val;
		}
		else if (R < mL || mR < L)
			return;
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			modify(mL, mR, val, i << 1, L, mid);
			modify(mL, mR, val, i << 1 | 1, mid + 1, R);
			seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
		}
	}

	pll query(int qL, int qR, int i = 1, int L = 0, int R = n - 1)
	{
		if (qL <= L && R <= qR)
			return seg[i];
		else if (R < qL || qR < L)
			return pll(1e9, n + 1);
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			return min(query(qL, qR, i << 1, L, mid),
					   query(qL, qR, i << 1 | 1, mid + 1, R));
		}
	}
	void safe_modify(int l, int r, ll val)
	{
		if (l <= r)
			modify(l, r, val);
		else
		{
			modify(l, n - 1, val);
			modify(0, r, val);
		}
	}
} seg, zero;

struct changeValseg
{
	ll seg[800005];

	void init(int i = 1, int L = 0, int R = n - 1)
	{
		seg[i] = -1;
		if (L == R)
			return;
		int mid = (L + R) / 2;
		init(i << 1, L, mid);
		init(i << 1 | 1, mid + 1, R);
	}

	void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = n - 1)
	{
		if (mL <= L && R <= mR)
			seg[i] = val;
		else if (R < mL || mR < L)
			return;
		else
		{
			if (seg[i] != -1)
			{
				seg[i << 1] = seg[i << 1 | 1] = seg[i];
				seg[i] = -1;
			}
			int mid = (L + R) / 2;
			modify(mL, mR, val, i << 1, L, mid);
			modify(mL, mR, val, i << 1 | 1, mid + 1, R);
		}
	}

	ll query(int pos, int i = 1, int L = 0, int R = n - 1)
	{
		if (seg[i] != -1 || L == R)
			return seg[i];
		else
		{
			int mid = (L + R) / 2;
			if (pos <= mid)
				return query(pos, i << 1, L, mid);
			else
				return query(pos, i << 1 | 1, mid + 1, R);
		}
	}

	void safe_modify(int l, int r, ll val)
	{
		if (l <= r)
			modify(l, r, val);
		else
		{
			modify(l, n - 1, val);
			modify(0, r, val);
		}
	}
} open, conceal;

const ll inf = 1e9;

void init(int k, vector<int> r)
{
	n = r.size();
	seg.init();
	zero.init();
	open.init();
	conceal.init();
	for (int i = 0; i < n; i++)
	{
		r[i] = k - 1 - r[i];
		seg.modify(i, i, r[i]);
		zero.modify(i, i, r[i]);
	}
	for (int it = 1; it <= n; it++)
	{
		{
			auto [v, p] = zero.query(0, n - 1);
			while (v == 0)
			{
				seg.safe_modify((p + 1) % n, (p + k - 1) % n, inf);
				zero.modify(p, p, inf);
				out[p] = open.query(p);
				tie(v, p) = zero.query(0, n - 1);
			}
		}
		int cur = seg.query(0, n - 1).S;
		in[cur] = conceal.query(cur);
		// cerr << cur << "->" << in[cur] << ' ' << out[cur] << '\n';
		seg.modify(cur, cur, inf);
		seg.safe_modify((cur + 1) % n, (cur + k - 1) % n, -inf);
		zero.safe_modify((cur - k + 1 + n) % n, cur, -1);
		seg.safe_modify((cur - k + 1 + n) % n, cur, -1);
		conceal.safe_modify((cur + 1) % n, (cur + k - 1) % n, cur);
		open.safe_modify((cur - k + 1 + n) % n, cur, cur);
		assert(order[cur] == 0);
		order[cur] = it;
	}

	vector<int> ord(n);
	for (int i = 0; i < n; i++)
		ord[order[i] - 1] = i;
	for (int i = n - 1; i >= 0; i--)
	{
		int u = ord[i];
		reachability[u][u] = 1;
		if (in[u] >= 0)
			reachability[in[u]] |= reachability[u];
		if (out[u] >= 0)
			reachability[out[u]] |= reachability[u];
	}
	return;
}

int compare_plants(int x, int y)
{
	if (reachability[x][y])
		return -1;
	if (reachability[y][x])
		return 1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25336 KB Output is correct
2 Correct 13 ms 25372 KB Output is correct
3 Correct 11 ms 25364 KB Output is correct
4 Correct 12 ms 25368 KB Output is correct
5 Correct 12 ms 25344 KB Output is correct
6 Correct 49 ms 29176 KB Output is correct
7 Correct 117 ms 81836 KB Output is correct
8 Runtime error 614 ms 101716 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 11 ms 25368 KB Output is correct
3 Correct 12 ms 25300 KB Output is correct
4 Correct 11 ms 25368 KB Output is correct
5 Correct 12 ms 25564 KB Output is correct
6 Correct 19 ms 27988 KB Output is correct
7 Correct 79 ms 43000 KB Output is correct
8 Correct 14 ms 25712 KB Output is correct
9 Correct 18 ms 27988 KB Output is correct
10 Correct 82 ms 42940 KB Output is correct
11 Correct 80 ms 42820 KB Output is correct
12 Correct 95 ms 43100 KB Output is correct
13 Correct 80 ms 42952 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25300 KB Output is correct
2 Correct 11 ms 25368 KB Output is correct
3 Correct 12 ms 25300 KB Output is correct
4 Correct 11 ms 25368 KB Output is correct
5 Correct 12 ms 25564 KB Output is correct
6 Correct 19 ms 27988 KB Output is correct
7 Correct 79 ms 43000 KB Output is correct
8 Correct 14 ms 25712 KB Output is correct
9 Correct 18 ms 27988 KB Output is correct
10 Correct 82 ms 42940 KB Output is correct
11 Correct 80 ms 42820 KB Output is correct
12 Correct 95 ms 43100 KB Output is correct
13 Correct 80 ms 42952 KB Output is correct
14 Correct 195 ms 81916 KB Output is correct
15 Runtime error 1484 ms 102584 KB Execution killed with signal 11
16 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 13 ms 25428 KB Output is correct
3 Correct 65 ms 35032 KB Output is correct
4 Runtime error 697 ms 101716 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25348 KB Output is correct
2 Correct 11 ms 25292 KB Output is correct
3 Correct 10 ms 25388 KB Output is correct
4 Correct 13 ms 25372 KB Output is correct
5 Correct 12 ms 25368 KB Output is correct
6 Correct 13 ms 25648 KB Output is correct
7 Correct 23 ms 27072 KB Output is correct
8 Correct 25 ms 27100 KB Output is correct
9 Correct 22 ms 27048 KB Output is correct
10 Correct 25 ms 27100 KB Output is correct
11 Correct 21 ms 27092 KB Output is correct
12 Correct 22 ms 27036 KB Output is correct
13 Correct 20 ms 27092 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25316 KB Output is correct
2 Correct 12 ms 25396 KB Output is correct
3 Correct 12 ms 25372 KB Output is correct
4 Correct 11 ms 25348 KB Output is correct
5 Correct 17 ms 27844 KB Output is correct
6 Runtime error 763 ms 101064 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 25336 KB Output is correct
2 Correct 13 ms 25372 KB Output is correct
3 Correct 11 ms 25364 KB Output is correct
4 Correct 12 ms 25368 KB Output is correct
5 Correct 12 ms 25344 KB Output is correct
6 Correct 49 ms 29176 KB Output is correct
7 Correct 117 ms 81836 KB Output is correct
8 Runtime error 614 ms 101716 KB Execution killed with signal 11
9 Halted 0 ms 0 KB -