oj.uz

Submission #303201

# Submission time Handle Problem Language Result Execution time Memory
303201 2020-09-20T01:31:23 Z tutis Comparing Plants (IOI20_plants) C++17
11 / 100
 4000 ms 219092 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;
	for (int i : K)
	{
		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 (C[x].contains(y))
		return 1;
	if (C[y].contains(x))
		return -1;
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40952 KB Output is correct
2 Correct 34 ms 40952 KB Output is correct
3 Correct 35 ms 40952 KB Output is correct
4 Correct 36 ms 40952 KB Output is correct
5 Correct 35 ms 41080 KB Output is correct
6 Correct 101 ms 43896 KB Output is correct
7 Execution timed out 4086 ms 219092 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 40952 KB Output is correct
2 Correct 37 ms 40952 KB Output is correct
3 Correct 37 ms 40960 KB Output is correct
4 Correct 35 ms 41080 KB Output is correct
5 Correct 84 ms 42232 KB Output is correct
6 Execution timed out 4082 ms 110500 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 40952 KB Output is correct
2 Correct 37 ms 40952 KB Output is correct
3 Correct 37 ms 40960 KB Output is correct
4 Correct 35 ms 41080 KB Output is correct
5 Correct 84 ms 42232 KB Output is correct
6 Execution timed out 4082 ms 110500 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 40952 KB Output is correct
2 Correct 36 ms 41080 KB Output is correct
3 Execution timed out 4089 ms 176740 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 40960 KB Output is correct
2 Correct 37 ms 40952 KB Output is correct
3 Correct 35 ms 41080 KB Output is correct
4 Correct 35 ms 41080 KB Output is correct
5 Correct 35 ms 41080 KB Output is correct
6 Correct 41 ms 41336 KB Output is correct
7 Correct 93 ms 43384 KB Output is correct
8 Correct 529 ms 49932 KB Output is correct
9 Correct 189 ms 46712 KB Output is correct
10 Correct 509 ms 49884 KB Output is correct
11 Correct 119 ms 44408 KB Output is correct
12 Correct 220 ms 47480 KB Output is correct
13 Correct 691 ms 54776 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 41080 KB Output is correct
3 Correct 35 ms 41080 KB Output is correct
4 Correct 35 ms 41080 KB Output is correct
5 Execution timed out 4064 ms 113016 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 40952 KB Output is correct
2 Correct 34 ms 40952 KB Output is correct
3 Correct 35 ms 40952 KB Output is correct
4 Correct 36 ms 40952 KB Output is correct
5 Correct 35 ms 41080 KB Output is correct
6 Correct 101 ms 43896 KB Output is correct
7 Execution timed out 4086 ms 219092 KB Time limit exceeded
8 Halted 0 ms 0 KB -