oj.uz

Submission #813294

# Submission time Handle Problem Language Result Execution time Memory
813294 2023-08-07T15:13:08 Z prvocislo Comparing Plants (IOI20_plants) C++17
5 / 100
 1525 ms 125776 KB 
#include "plants.h"
#include <iostream>
#include <algorithm>
#include <set>
#include <string>
#include <vector>
typedef long long ll;
using namespace std;

const int maxn = 1 << 19, logn = 19, inf = 1e9 + 5;
vector<pair<int, int> > mini(maxn * 2, { inf, -1 });
vector<int> l(maxn * 2), r(maxn * 2), lz(maxn * 2, 0);
void add(int li, int ri, int x, int vr = 1)
{
	if (ri < l[vr] || r[vr] < li) return;
	if (li <= l[vr] && r[vr] <= ri) return lz[vr] += x, mini[vr].first += x, void();
	add(li, ri, x, (vr << 1)), add(li, ri, x, (vr << 1) | 1);
	mini[vr] = min(mini[vr << 1], mini[(vr << 1) | 1]), mini[vr].first += lz[vr];
}
int n, k;
pair<int, int> query(int li, int ri, int vr = 1)
{
	if (ri < l[vr] || r[vr] < li) return { inf, -1 };
	if (li <= l[vr] && r[vr] <= ri) return mini[vr];
	return min(query(li, ri, vr << 1), query(li, ri, (vr << 1) | 1));
}
vector<int> ord;
set<int> v0; set<pair<int, int> > ordv; // {vzdialenost od predoslej 0, pozicia}
pair<int, int> give_pair(int x)
{
	if (v0.empty()) return { n, x };
	if (x <= *v0.begin()) return { n + x - *prev(v0.end()), x };
	return { x - *prev(v0.lower_bound(x)), x };
}
void pridaj(int x)
{
	auto nx = v0.upper_bound(x);
	if (!v0.empty() && nx == v0.end()) nx = v0.begin();
	int val = (nx == v0.end() || *nx == x ? -1 : *nx);
	if (val != -1) ordv.erase(give_pair(val));
	v0.insert(x), ordv.insert(give_pair(x));
	if (val != -1) ordv.insert(give_pair(val));
}
void zober(int x)
{
	auto nx = v0.upper_bound(x);
	if (!v0.empty() && nx == v0.end()) nx = v0.begin();
	int val = (nx == v0.end() || *nx == x ? -1 : *nx);
	if (val != -1) ordv.erase(give_pair(val));
	ordv.erase(give_pair(x)), v0.erase(x);
	if (val != -1) ordv.insert(give_pair(val));
}
vector<vector<int> > hl(logn, vector<int>(maxn, 0)), hr(logn, vector<int>(maxn, 0));
void init(int K, vector<int> h)
{
	n = h.size(), k = K;
	ord.resize(n, -1);
	for (int i = 0; i < n; i++)
	{
		if (h[i]) mini[maxn + i] = { h[i], i };
		else pridaj(i);
	}
	for (int i = maxn; i < maxn * 2; i++) l[i] = r[i] = i - maxn;
	for (int i = maxn - 1; i; i--) l[i] = l[i * 2], r[i] = r[i * 2 + 1], mini[i] = min(mini[i * 2], mini[i * 2 + 1]);
	for (int i = n - 1; i >= 0; i--)
	{
		int id = prev(ordv.end())->second;
		ord[id] = i;
		zober(id);
		add(id - (k - 1), id - 1, -1), add(n + id - (k - 1), n - 1, -1);
		while (mini[1].first == 0)
		{
			int x = mini[1].second;
			add(x, x, inf), pridaj(x);
		}
	}
	vector<pair<int, int> > pr;
	for (int i = 0; i < 2 * n; i++) mini[maxn + i] = { ord[i % n], i }, pr.push_back({ ord[i % n], i });
	for (int i = maxn - 1; i; i--) mini[i] = min(mini[i << 1], mini[(i << 1) | 1]);
	sort(pr.begin(), pr.end());
	for (pair<int, int> pp : pr)
	{
		int i = pp.second;
		hl[0][i] = query(i - k + 1, i - 1).second, hr[0][i] = query(i + 1, i + k - 1).second;
		if (hl[0][i] == -1) hl[0][i] = i;
		if (hr[0][i] == -1) hr[0][i] = i;
		add(i, i, inf);
	}
	for (int j = 1; j < logn; j++) for (int i = 0; i < 2 * n; i++) hr[j][i] = hr[j - 1][hr[j - 1][i]], hl[j][i] = hl[j - 1][hl[j - 1][i]];
}
int higher(int x, int y) // plati x < y
{
	int x2 = x;
	for (int j = logn - 1; j >= 0; j--) if (hr[j][x] <= y) x = hr[j][x];
	if (ord[x % n] <= ord[y % n] && abs(y - x) < k) return 1;
	x = x2;
	for (int j = logn - 1; j >= 0; j--) if (hl[j][y] >= x) y = hl[j][y];
	if (ord[x % n] >= ord[y % n] && abs(y - x) < k) return -1;
	return 0;
}
int compare_plants(int x, int y)
{
	int h1 = higher(y, x + n), h2 = -higher(x, y);
	if (h1 != 0) return h1;
	if (h2 != 0) return h2;
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100920 KB Output is correct
2 Correct 40 ms 100808 KB Output is correct
3 Correct 40 ms 100904 KB Output is correct
4 Correct 48 ms 100828 KB Output is correct
5 Correct 41 ms 100828 KB Output is correct
6 Correct 139 ms 103140 KB Output is correct
7 Correct 325 ms 105188 KB Output is correct
8 Correct 1525 ms 116332 KB Output is correct
9 Correct 1339 ms 115980 KB Output is correct
10 Correct 1356 ms 116148 KB Output is correct
11 Correct 1284 ms 117180 KB Output is correct
12 Correct 1235 ms 116788 KB Output is correct
13 Correct 1371 ms 125776 KB Output is correct
14 Correct 892 ms 113864 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 100904 KB Output is correct
2 Correct 46 ms 100912 KB Output is correct
3 Correct 46 ms 100912 KB Output is correct
4 Correct 45 ms 100896 KB Output is correct
5 Incorrect 45 ms 100904 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 100904 KB Output is correct
2 Correct 46 ms 100912 KB Output is correct
3 Correct 46 ms 100912 KB Output is correct
4 Correct 45 ms 100896 KB Output is correct
5 Incorrect 45 ms 100904 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

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

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 100944 KB Output is correct
2 Correct 47 ms 100916 KB Output is correct
3 Correct 47 ms 100888 KB Output is correct
4 Incorrect 48 ms 100912 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 100868 KB Output is correct
2 Correct 48 ms 100856 KB Output is correct
3 Correct 51 ms 100808 KB Output is correct
4 Incorrect 46 ms 100864 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 100920 KB Output is correct
2 Correct 40 ms 100808 KB Output is correct
3 Correct 40 ms 100904 KB Output is correct
4 Correct 48 ms 100828 KB Output is correct
5 Correct 41 ms 100828 KB Output is correct
6 Correct 139 ms 103140 KB Output is correct
7 Correct 325 ms 105188 KB Output is correct
8 Correct 1525 ms 116332 KB Output is correct
9 Correct 1339 ms 115980 KB Output is correct
10 Correct 1356 ms 116148 KB Output is correct
11 Correct 1284 ms 117180 KB Output is correct
12 Correct 1235 ms 116788 KB Output is correct
13 Correct 1371 ms 125776 KB Output is correct
14 Correct 892 ms 113864 KB Output is correct
15 Correct 49 ms 100904 KB Output is correct
16 Correct 46 ms 100912 KB Output is correct
17 Correct 46 ms 100912 KB Output is correct
18 Correct 45 ms 100896 KB Output is correct
19 Incorrect 45 ms 100904 KB Output isn't correct
20 Halted 0 ms 0 KB -