oj.uz

Submission #303202

# Submission time Handle Problem Language Result Execution time Memory
303202 2020-09-20T01:33:31 Z tutis Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 217976 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
{
	set<int>A;
	inter() {}
	void add(int i)
	{
		A.insert(i);
	}
	bool contains(int c)
	{
		if (A.count(c))
			return true;
		return false;
	}
};
inter merge(const inter &a, const inter &b)
{
	inter c = a;
	for (int t : b.A)
		c.add(t);
	return c;
}
struct ST1
{
	int l, r;
	inter lazy;
	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 fix()
	{
		if (l < r)
		{
			left->lazy = merge(left->lazy, lazy);
			right->lazy = merge(right->lazy, lazy);
			lazy = inter();
		}
	}
	void add(int x, int y, inter g)
	{
		if (x <= l && r <= y)
		{
			lazy = merge(lazy, g);
			return fix();
		}
		fix();
		if (y < l || r < x)
			return;
		left->add(x, y, g);
		right->add(x, y, g);
	}
	inter get(int x)
	{
		if (l == r)
			return lazy;
		fix();
		if (x <= (l + r) / 2)
			return left->get(x);
		else
			return right->get(x);
	}
} mediss(0, 200000);
void adddd(int x, int y, inter c)
{
	while (y >= n)
	{
		x -= n;
		y -= n;
	}
	while (x < 0)
	{
		x += n;
		y += n;
	}
	if (y < n)
	{
		return mediss.add(x, y, c);
	}
	else
	{
		mediss.add(x, n - 1, c);
		mediss.add(0, y - n, c);
	}
}
inter C[200000];
void init(int k, vector<int> r)
{
	K = k;
	n = r.size();
	N = 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);
	}
	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;
	int timer = 0;
	for (int i : K)
	{
		id[i] = timer++;
		inter c = mediss.get(i);
		c.add(i);
		C[i] = c;
		adddd(i - (k - 1), i + (k - 1), c);
	}
}

int compare_plants(int x, int y)
{
	if (id[x] < id[y])
		return -compare_plants(y, x);
	if (C[x].contains(y))
		return 1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40956 KB Output is correct
2 Correct 34 ms 40952 KB Output is correct
3 Correct 34 ms 41080 KB Output is correct
4 Correct 34 ms 41024 KB Output is correct
5 Correct 34 ms 40952 KB Output is correct
6 Correct 102 ms 43896 KB Output is correct
7 Execution timed out 4091 ms 217976 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 41080 KB Output is correct
2 Correct 36 ms 41004 KB Output is correct
3 Correct 36 ms 41088 KB Output is correct
4 Correct 34 ms 40952 KB Output is correct
5 Correct 85 ms 42232 KB Output is correct
6 Execution timed out 4046 ms 109176 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 41080 KB Output is correct
2 Correct 36 ms 41004 KB Output is correct
3 Correct 36 ms 41088 KB Output is correct
4 Correct 34 ms 40952 KB Output is correct
5 Correct 85 ms 42232 KB Output is correct
6 Execution timed out 4046 ms 109176 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40952 KB Output is correct
2 Correct 37 ms 41028 KB Output is correct
3 Execution timed out 4072 ms 173268 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 41080 KB Output is correct
2 Correct 35 ms 40964 KB Output is correct
3 Correct 36 ms 40952 KB Output is correct
4 Correct 38 ms 41080 KB Output is correct
5 Correct 35 ms 41088 KB Output is correct
6 Correct 41 ms 41336 KB Output is correct
7 Correct 97 ms 43384 KB Output is correct
8 Correct 530 ms 49912 KB Output is correct
9 Correct 197 ms 46712 KB Output is correct
10 Correct 505 ms 49784 KB Output is correct
11 Correct 116 ms 44536 KB Output is correct
12 Correct 217 ms 47548 KB Output is correct
13 Correct 693 ms 54520 KB Output is correct

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 41080 KB Output is correct
2 Correct 35 ms 41084 KB Output is correct
3 Correct 35 ms 40952 KB Output is correct
4 Correct 44 ms 41080 KB Output is correct
5 Execution timed out 4083 ms 113048 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40956 KB Output is correct
2 Correct 34 ms 40952 KB Output is correct
3 Correct 34 ms 41080 KB Output is correct
4 Correct 34 ms 41024 KB Output is correct
5 Correct 34 ms 40952 KB Output is correct
6 Correct 102 ms 43896 KB Output is correct
7 Execution timed out 4091 ms 217976 KB Time limit exceeded
8 Halted 0 ms 0 KB -