oj.uz

Submission #1020283

# Submission time Handle Problem Language Result Execution time Memory
1020283 2024-07-11T19:26:57 Z j_vdd16 Comparing Plants (IOI20_plants) C++17
0 / 100
 33 ms 5096 KB 
#include <algorithm>
#include <bitset>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <limits.h>
#include <math.h>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>

//#define int long long
#define loop(X, N) for(int X = 0; X < (N); X++)
#define all(V) V.begin(), V.end()
#define rall(V) V.rbegin(), V.rend()

using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vector<ii>> vvii;
typedef vector<bool> vb;
typedef vector<vector<bool>> vvb;

typedef uint64_t u64;
typedef int64_t i64;

int k;
struct SegTree {
	const ii id = { INT_MAX, 0 };
	vii tree;
	vi lazySub;
	int n, N;

	SegTree(vi v) {
		n = v.size();
		N = 1;
		while (N < n)
			N *= 2;

		tree.resize(2 * N, id);
		lazySub.resize(2 * N, 0);
		loop(i, n)
			tree[N + i] = { v[i], i };

		for (int i = N - 1; i >= 1; i--)
			tree[i] = merge(tree[2 * i], tree[2 * i + 1]);
	}

	ii merge(ii a, ii b) {
		if (a.first < b.first)
			return a;

		if (b.first < a.first || b.second - a.second >= k)
			return b;

		return a;
	}

	void rangeSub(int l, int r, int v, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		if (tl >= r || tr <= l)
			return;

		if (tl >= l && tr <= r)
		{
			tree[i].first -= v;
			lazySub[i] += v;
			return;
		}

		int tm = (tl + tr) / 2;
		rangeSub(l, r, v, i * 2, tl, tm);
		rangeSub(l, r, v, i * 2 + 1, tm, tr);

		tree[i] = merge(tree[i * 2], tree[i * 2 + 1]);
	}
	ii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

		if (tl >= r || tr <= l)
			return id;

		if (i < N)
		{
			lazySub[2 * i] += lazySub[i];
			lazySub[2 * i + 1] += lazySub[i];
			tree[2 * i].first -= lazySub[i];
			tree[2 * i + 1].first -= lazySub[i];
		}
		lazySub[i] = 0;

		if (tl >= l && tr <= r)
			return tree[i];

		int tm = (tl + tr) / 2;
		return merge(range(l, r, i * 2, tl, tm), range(l, r, i * 2 + 1, tm, tr));
	}

	void set(int pos, int v, int i = 1, int tl = 0, int tr = -1)
	{
		if (tr == -1)
			tr = N;

		if (i >= N)
		{
			tree[i].first = v;
			return;
		}

		lazySub[2 * i] += lazySub[i];
		lazySub[2 * i + 1] += lazySub[i];
		tree[2 * i].first -= lazySub[i];
		tree[2 * i + 1].first -= lazySub[i];
		lazySub[i] = 0;

		int tm = (tl + tr) / 2;
		if (pos < tm)
			set(pos, v, i * 2, tl, tm);
		else
			set(pos, v, i * 2 + 1, tm, tr);

		tree[i] = merge(tree[2 * i + 1], tree[2 * i]);
	}
};

int n;
vi r;

vi perm;
void init(int _k, vi _r)
{
	n = _r.size();
	k = _k;
	r = _r;
	perm.assign(n, 0);

	SegTree segTree(r);

	int idx = n;
	vb vis(n);

	/*cout << "R: ";
	for (int x : r)
		cout << x << ' ';
	cout << endl;
	cout << "Low: ";*/
	while (idx > 0)
	{
		/*vi lowest;
		int count = 0;
		for (int i = 1; i < k; i++)
			count += vis[i];

		loop(i, n)
		{
			if (r[i] == count && !vis[i])
				lowest.push_back(i);

			count -= vis[(i + 1) % n];
			count += vis[(i + k) % n];
		}*/

		/*int n2 = lowest.size();
		int low = lowest[0];
		loop(i, n2 - 1)
		{
			if (lowest[i + 1] - lowest[i] >= k)
			{
				low = lowest[i + 1];
				break;
			}
		}*/

		auto [lowVal, low] = segTree.range(0, n);
		//cout << low << ' ';
		if (low - k + 1 < 0)
		{
			segTree.rangeSub(0, low, 1);
			segTree.rangeSub(n + low - k + 1, n, 1);
		}
		else
		{
			segTree.rangeSub(low - k + 1, low, 1);
		}

		segTree.set(low, INT_MAX / 2);
		vis[low] = true;
		perm[low] = idx--;
	}
	//cout << endl;
}

int compare_plants(int x, int y)
{
	if (perm[x] < perm[y])
		return -1;

	if (perm[x] > perm[y])
		return 1;

	return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Incorrect 33 ms 5096 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

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