oj.uz

Submission #303185

# Submission time Handle Problem Language Result Execution time Memory
303185 2020-09-20T00:35:02 Z tutis Comparing Plants (IOI20_plants) C++17
32 / 100
 2040 ms 2097156 KB 
#include "plants.h"
#include <bits/stdc++.h>
using namespace std;
vector<int>k0, k1;
int K, n;
vector<int>A;
struct ST
{
	int l, r;
	pair<int, int> mn;
	pair<int, int> mn1;
	int del = 0;
	int del1 = 0;
	ST *left, *right;
	ST(int l, int r, vector<int>&a): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST(l, (l + r) / 2, a);
			right = new ST((l + r) / 2 + 1, r, a);
			mn = min(left->mn, right->mn);
		}
		else
			mn = {a[l], l};
		mn1 = mn;
	}
	void fix()
	{
		if (l == r)
		{
			mn.first += del;
			del = 0;
		}
		else
		{
			mn.first += del;
			left->del += del;
			right->del += del;
			del = 0;
		}
	}
	void fix1()
	{
		if (l == r)
		{
			mn1.first += del1;
			del1 = 0;
		}
		else
		{
			mn1.first += del1;
			left->del1 += del1;
			right->del1 += del1;
			del1 = 0;
		}
	}
	void add(int x, int y, int w)
	{
		if (x <= l && r <= y)
		{
			del += w;
			return fix();
		}
		fix();
		if (r < x || y < l)
			return;
		left->add(x, y, w);
		right->add(x, y, w);
		mn = min(left->mn, right->mn);
	}
	void add1(int x, int y, int w)
	{
		if (x <= l && r <= y)
		{
			del1 += w;
			return fix1();
		}
		fix1();
		if (r < x || y < l)
			return;
		left->add1(x, y, w);
		right->add1(x, y, w);
		mn1 = min(left->mn1, right->mn1);
	}
};
int id[200000];
int N;
struct inter
{
	vector<pair<int, int>>A;
	inter() {}
	void add(int i)
	{
		A.push_back({i, i});
	}
	bool contains(int c)
	{
		for (auto i : A)
			if (i.first <= c && c <= i.second)
				return true;
		return false;
	}
};
inter merge(inter a, inter b)
{
	for (pair<int, int>g : b.A)
		a.A.push_back(g);
	return a;
}
struct ST1
{
	int l, r;
	inter xx;
	ST1 *left, *right;
	ST1(int l, int r): l(l), r(r)
	{
		if (l < r)
		{
			left = new ST1(l, (l + r) / 2);
			right = new ST1((l + r) / 2 + 1, r);
		}
	}
	void set(int i, inter g)
	{
		if (l == r)
		{
			xx = g;
		}
		else
		{
			if (i <= (l + r) / 2)
				left->set(i, g);
			else
				right->set(i, g);
			xx = merge(left->xx, right->xx);
		}
	}
	inter get(int x, int y)
	{
		if (x <= l && r <= y)
			return xx;
		if (y < l || r < x)
			return inter();
		return merge(left->get(x, y), right->get(x, y));
	}
} mediss(0, 200000);
inter gett(int x, int y)
{
	while (y >= n)
	{
		x -= n;
		y -= n;
	}
	while (x < 0)
	{
		x += n;
		y += n;
	}
	if (y < n)
	{
		return mediss.get(x, y);
	}
	else
	{
		return merge(mediss.get(x, n - 1), mediss.get(0, y - n));
	}
}
void init(int k, vector<int> r)
{
	K = k;
	n = r.size();
	N = n;
	if (k == 2)
	{
		k0 = k1 = vector<int>(n, 0);
		for (int t = 0; t < 2; t++)
			for (int i = n - 1; i >= 0; i--)
			{
				if (r[i] == 0)
					k0[i] = 1 + k0[(i + 1) % n];
				else
					k1[i] = 1 + k1[(i + 1) % n];
			}
		return;
	}
	if (2 * k > n)
	{
		ST medis(0, n - 1, r);
		auto add = [&](int x, int y, int w)
		{
			while (y >= n)
			{
				x -= n;
				y -= n;
			}
			while (x < 0)
			{
				x += n;
				y += n;
			}
			if (y < n)
			{
				medis.add(x, y, w);
			}
			else
			{
				medis.add(x, n - 1, w);
				medis.add(0, y - n, w);
			}
		};
		auto add1 = [&](int x, int y, int w)
		{
			while (y >= n)
			{
				x -= n;
				y -= n;
			}
			while (x < 0)
			{
				x += n;
				y += n;
			}
			if (y < n)
			{
				medis.add1(x, y, w);
			}
			else
			{
				medis.add1(x, n - 1, w);
				medis.add1(0, y - n, w);
			}
		};
		while (medis.mn1.first == 0)
		{
			int i = medis.mn1.second;
			add(i + 1, i + (k - 1), 1);
			add1(i, i, 1);
		}
		A = vector<int>(n, -1);
		for (int tt = 0; tt < n; tt++)
		{
			while (medis.mn1.first == 0)
			{
				int i = medis.mn1.second;
				add(i + 1, i + (k - 1), 1);
				add1(i, i, 1);
			}
			int i = medis.mn.second;
			add(i + 1, i + (k - 1), -1);
			add(i - (k - 1), i - 1, -1);
			add1(i - (k - 1), i - 1, -1);
			A[i] = tt;
			add(i, i, n + 10000);
			add1(i, i, n + 10000);
			r[i] = n + 100;
		}
		return;
	}
	ST medis(0, n - 1, r);
	auto add = [&](int x, int y, int w)
	{
		while (y >= n)
		{
			x -= n;
			y -= n;
		}
		while (x < 0)
		{
			x += n;
			y += n;
		}
		if (y < n)
		{
			medis.add(x, y, w);
		}
		else
		{
			medis.add(x, n - 1, w);
			medis.add(0, y - n, w);
		}
	};
	auto add1 = [&](int x, int y, int w)
	{
		while (y >= n)
		{
			x -= n;
			y -= n;
		}
		while (x < 0)
		{
			x += n;
			y += n;
		}
		if (y < n)
		{
			medis.add1(x, y, w);
		}
		else
		{
			medis.add1(x, n - 1, w);
			medis.add1(0, y - n, w);
		}
	};
	while (medis.mn1.first == 0)
	{
		int i = medis.mn1.second;
		add(i + 1, i + (k - 1), 1);
		add1(i, i, 1);
	}
	vector<int>K;
	for (int tt = 0; tt < n; tt++)
	{
		while (medis.mn1.first == 0)
		{
			int i = medis.mn1.second;
			add(i + 1, i + (k - 1), 1);
			add1(i, i, 1);
		}
		int i = medis.mn.second;
		add(i + 1, i + (k - 1), -1);
		add(i - (k - 1), i - 1, -1);
		add1(i - (k - 1), i - 1, -1);
		add(i, i, n + 10000);
		add1(i, i, n + 10000);
		id[i] = tt;
		K.push_back(i);
		r[i] = n + 100;
	}
	reverse(K.begin(), K.end());
	vector<int>ok;
	for (int i : K)
	{
		inter c = gett(i - (k - 1), i + (k - 1));
		c.add(i);
		mediss.set(i, c);
	}
}

int compare_plants(int x, int y)
{
	assert(x < y);
	if (K == 2)
	{
		if (k0[x] >= y - x)
			return 1;
		if (k1[x] >= y - x)
			return -1;
		if (k0[y] >= n - y + x)
			return -1;
		if (k1[y] >= n - y + x)
			return 1;
		return 0;
	}
	if (!A.empty())
	{
		if (A[x] < A[y])
			return 1;
		else
			return -1;
	}
	if (mediss.get(x, x).contains(y))
		return 1;
	if (mediss.get(y, y).contains(x))
		return 1;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25336 KB Output is correct
2 Correct 25 ms 25344 KB Output is correct
3 Correct 26 ms 25464 KB Output is correct
4 Correct 25 ms 25344 KB Output is correct
5 Correct 25 ms 25336 KB Output is correct
6 Correct 90 ms 28152 KB Output is correct
7 Correct 112 ms 28496 KB Output is correct
8 Correct 132 ms 30840 KB Output is correct
9 Correct 135 ms 30968 KB Output is correct
10 Correct 132 ms 30840 KB Output is correct
11 Correct 134 ms 30840 KB Output is correct
12 Correct 130 ms 30840 KB Output is correct
13 Correct 127 ms 30840 KB Output is correct
14 Correct 132 ms 30840 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25344 KB Output is correct
2 Correct 25 ms 25376 KB Output is correct
3 Correct 25 ms 25344 KB Output is correct
4 Correct 25 ms 25344 KB Output is correct
5 Correct 27 ms 25344 KB Output is correct
6 Correct 30 ms 25592 KB Output is correct
7 Correct 118 ms 28920 KB Output is correct
8 Correct 28 ms 25472 KB Output is correct
9 Correct 30 ms 25600 KB Output is correct
10 Correct 117 ms 28920 KB Output is correct
11 Correct 113 ms 28828 KB Output is correct
12 Correct 116 ms 29048 KB Output is correct
13 Correct 114 ms 28952 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25344 KB Output is correct
2 Correct 25 ms 25376 KB Output is correct
3 Correct 25 ms 25344 KB Output is correct
4 Correct 25 ms 25344 KB Output is correct
5 Correct 27 ms 25344 KB Output is correct
6 Correct 30 ms 25592 KB Output is correct
7 Correct 118 ms 28920 KB Output is correct
8 Correct 28 ms 25472 KB Output is correct
9 Correct 30 ms 25600 KB Output is correct
10 Correct 117 ms 28920 KB Output is correct
11 Correct 113 ms 28828 KB Output is correct
12 Correct 116 ms 29048 KB Output is correct
13 Correct 114 ms 28952 KB Output is correct
14 Correct 198 ms 30968 KB Output is correct
15 Correct 1653 ms 55288 KB Output is correct
16 Correct 196 ms 30968 KB Output is correct
17 Correct 1614 ms 55288 KB Output is correct
18 Correct 1085 ms 55288 KB Output is correct
19 Correct 1082 ms 55180 KB Output is correct
20 Correct 1367 ms 55288 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25344 KB Output is correct
2 Incorrect 47 ms 41800 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25344 KB Output is correct
2 Correct 25 ms 25344 KB Output is correct
3 Correct 25 ms 25336 KB Output is correct
4 Incorrect 25 ms 25344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 25336 KB Output is correct
2 Correct 25 ms 25344 KB Output is correct
3 Correct 25 ms 25336 KB Output is correct
4 Correct 25 ms 25344 KB Output is correct
5 Runtime error 2040 ms 2097156 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 25336 KB Output is correct
2 Correct 25 ms 25344 KB Output is correct
3 Correct 26 ms 25464 KB Output is correct
4 Correct 25 ms 25344 KB Output is correct
5 Correct 25 ms 25336 KB Output is correct
6 Correct 90 ms 28152 KB Output is correct
7 Correct 112 ms 28496 KB Output is correct
8 Correct 132 ms 30840 KB Output is correct
9 Correct 135 ms 30968 KB Output is correct
10 Correct 132 ms 30840 KB Output is correct
11 Correct 134 ms 30840 KB Output is correct
12 Correct 130 ms 30840 KB Output is correct
13 Correct 127 ms 30840 KB Output is correct
14 Correct 132 ms 30840 KB Output is correct
15 Correct 25 ms 25344 KB Output is correct
16 Correct 25 ms 25376 KB Output is correct
17 Correct 25 ms 25344 KB Output is correct
18 Correct 25 ms 25344 KB Output is correct
19 Correct 27 ms 25344 KB Output is correct
20 Correct 30 ms 25592 KB Output is correct
21 Correct 118 ms 28920 KB Output is correct
22 Correct 28 ms 25472 KB Output is correct
23 Correct 30 ms 25600 KB Output is correct
24 Correct 117 ms 28920 KB Output is correct
25 Correct 113 ms 28828 KB Output is correct
26 Correct 116 ms 29048 KB Output is correct
27 Correct 114 ms 28952 KB Output is correct
28 Correct 198 ms 30968 KB Output is correct
29 Correct 1653 ms 55288 KB Output is correct
30 Correct 196 ms 30968 KB Output is correct
31 Correct 1614 ms 55288 KB Output is correct
32 Correct 1085 ms 55288 KB Output is correct
33 Correct 1082 ms 55180 KB Output is correct
34 Correct 1367 ms 55288 KB Output is correct
35 Correct 25 ms 25344 KB Output is correct
36 Incorrect 47 ms 41800 KB Output isn't correct
37 Halted 0 ms 0 KB -