oj.uz

답안 #1050481

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1050481 2024-08-09T10:06:06 Z aykhn 식물 비교 (IOI20_plants) C++17
0 / 100
 64 ms 72896 KB 
#include "plants.h"
#include <bits/stdc++.h>
 
using namespace std;
 
const int MXN = 2e5 + 5;
const int LOG = 20;

#define inf 0x3F3F3F3F
 
int n;
array<int, 2> p[2][LOG][MXN];
int in[2][MXN], out[2][MXN], tim[2], used[2];
int a[MXN], cnt[MXN], rr[MXN], f[MXN];
array<int, 2> st[MXN << 2];
int lz[MXN << 2];

void build(int l, int r, int x)
{
	if (l == r)
	{
		st[x] = {cnt[l] - rr[l], l};
		return;
	}
	int mid = (l + r) >> 1;
	build(l, mid, 2*x);
	build(mid + 1, r, 2*x + 1);
	st[x] = min(st[2*x], st[2*x + 1]);
}
void relax(int l, int r, int x)
{
	if (!lz[x]) return;
	st[x][0] += lz[x];
	if (l == r)
	{
		lz[x] = 0;
		return;
	}
	lz[2*x] += lz[x], lz[2*x + 1] += lz[x];
	lz[x] = 0;
}
void upd(int l, int r, int x, int lx, int rx, int val)
{
	if (lx > rx) return;
	relax(l, r, x);
	if (l > rx || r < lx) return;
	if (l >= lx && r <= rx)
	{
		lz[x] += val;
		relax(l, r, x);
		return;
	}
	int mid = (l + r) >> 1;
	upd(l, mid, 2*x, lx, rx, val);
	upd(mid + 1, r, 2*x + 1, lx, rx, val);
	st[x] = min(st[2*x], st[2*x + 1]);
}

set<int> idx;
set<array<int, 2>> dif;

void ins(int x)
{
	idx.insert(x);
	if (idx.size() == 1)
	{
		dif.insert({0, x});
		return;
	}
	auto it = idx.find(x);
	auto itl = it, itr = it;
	if (it == idx.begin()) itl = prev(idx.end());
	else itl = prev(it);
	if (next(it) == idx.end()) itr = idx.begin();
	else itr = next(it);
	dif.erase({(*itr - *itl + n) % n, *itr});
	dif.insert({(x - *itl + n) % n, x});
	dif.insert({(*itr - x + n) % n, *itr});
}
void ers(int x)
{
	if (idx.size() == 1)
	{
		idx.clear();
		dif.clear();
		return;
	}
	auto it = idx.find(x);
	auto itl = it, itr = it;
	if (it == idx.begin()) itl = prev(idx.end());
	else itl = prev(it);
	if (next(it) == idx.end()) itr = idx.begin();
	else itr = next(it);
	dif.erase({(x - *itl + n) % n, x});
	dif.erase({(*itr - x + n) % n, *itr});
	dif.insert({(*itr - *itl + n) % n, *itr});
	idx.erase(it);
}
// 4 3 2
// 0 1 1 2
// 0 2
// 1 2

 
void init(int k, vector<int> r) 
{
	n = r.size();
	f[n] = inf;
	for (int i = 1; i <= (n * 4); i++) st[i] = {inf, -1};
	for (int i = 0; i < n; i++) rr[i] = r[i];
	for (int i = 0; i < n; i++) cnt[i] = k - 1;
	build(0, n - 1, 1);
	while (1)
	{
		array<int, 2> x = st[1];
		if (!x[1]) break;
		if (!x[0]) 
		{
			ins(x[1]);
			upd(0, n - 1, 1, x[1], x[1], inf);
		}
		else break;
	}
	int cur = 0;
	while (!idx.empty())
	{
		int ind = (*dif.rbegin())[1];
		ers(ind);
		f[ind] = ++cur;
		if (ind - 1 >= 0) upd(0, n - 1, 1, max(ind - k + 1, 0), ind - 1, -1);
		if (ind - k + 1 < 0) upd(0, n - 1, 1, (ind - k + 1 + n) % n, n - 1, -1);
		// for (int i = (idx[ind] - 1 + n) % n; i != idx[(ind - 1 + sz) % sz]; i = (i - 1 + n) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// }
		// for (int i = (idx[ind] + 1) % n; i != (idx[ind] + k) % n; i = (i + 1) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// }
		// for (int i = (idx[ind] - 1 + n) % n; i != (idx[ind] - k + n) % n; i = (i - 1 + n) % n)
		// {
		// 	if (!f[i]) adj[idx[ind]].push_back(i);
		// 	cnt[i]--;
		// }
		// f[idx[ind]] = 1;
		while (1)
		{
			array<int, 2> x = st[1];
			if (!x[0]) 
			{
				ins(x[1]);
				upd(0, n - 1, 1, x[1], x[1], inf);
			}
			else break;
		}
	}
	set<array<int, 2>> s;
	for (int i = 0; i < k; i++) s.insert({f[i], i});
	for (int i = n - 1; i >= 0; i--)
	{
		s.erase({f[(i + k) % n], (i + k) % n});
		auto it = s.lower_bound({f[i], i});
		if (it != s.end()) 
		{
			p[0][0][i] = {(*it)[1], ((*it)[1] - i + n) % n};
		}
		else p[0][0][i] = {n, inf};
		s.insert({f[i], i});
	}
	s.clear();
	for (int i = n - k; i < n; i++) s.insert({f[i], i});
	for (int i = 0; i < n; i++)
	{
		s.erase({f[(i - k + n) % n], (i - k + n) % n});
		auto it = s.lower_bound({f[i], i});
		if (it != s.end()) 
		{
			p[1][0][i] = {(*it)[1], (i - (*it)[1] + n) % n};
		}
		else p[1][0][i] = {n, inf};
		s.insert({f[i], i});
	}
	for (int j = 0; j < 2; j++)
	{
		for (int i = 1; i < LOG; i++)
		{
			for (int k = 0; k < n; k++)
			{
				int par = p[j][i - 1][k][0];
				p[j][i][k] = {p[j][i - 1][par][0], p[j][i - 1][par][1] + p[j][i - 1][k][1]};
			}
		}
	}
}

int check(int x, int y)
{
	int x1 = x;
	int d = (y - x + n) % n;
	int res = 0;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (f[p[0][i][x][0]] <= f[y]) 
		{
			res += p[0][i][x][1];
			x = p[0][i][x][0];
		}
	}
	if (f[x] <= f[y] && res >= d) return 1;
	d = (x - y + n) % n;
	res = 0, x = x1;
	for (int i = LOG - 1; i >= 0; i--)
	{
		if (f[p[1][i][x][0]] <= f[y]) 
		{
			res += p[1][i][x][1];
			x = p[1][i][x][0];
		}
	}
	return (f[x] <= f[y] && res >= d);
}

int compare_plants(int x, int y) 
{
	// ? x < y
	if (check(x, y)) return -1;
	if (check(y, x)) return 1;
	return 0;
	// return (a[x] > a[y] ? 1 : -1);
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 69980 KB Output is correct
2 Correct 5 ms 69980 KB Output is correct
3 Incorrect 5 ms 69976 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 69976 KB Output is correct
2 Correct 5 ms 69980 KB Output is correct
3 Correct 5 ms 69980 KB Output is correct
4 Incorrect 5 ms 69980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 69976 KB Output is correct
2 Correct 5 ms 69980 KB Output is correct
3 Correct 5 ms 69980 KB Output is correct
4 Incorrect 5 ms 69980 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 69980 KB Output is correct
2 Correct 5 ms 69980 KB Output is correct
3 Incorrect 64 ms 72896 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 69976 KB Output is correct
2 Correct 5 ms 69980 KB Output is correct
3 Incorrect 5 ms 69980 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 69976 KB Output is correct
2 Correct 5 ms 69980 KB Output is correct
3 Incorrect 5 ms 70112 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 69980 KB Output is correct
2 Correct 5 ms 69980 KB Output is correct
3 Incorrect 5 ms 69976 KB Output isn't correct
4 Halted 0 ms 0 KB -