oj.uz

Submission #800292

# Submission time Handle Problem Language Result Execution time Memory
800292 2023-08-01T13:11:14 Z LittleCube Comparing Plants (IOI20_plants) C++17
0 / 100
 31 ms 51276 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
#define ll long long
using namespace std;

int n, state[800005], order[200005];

struct segTree
{
	pll seg[800005];
	ll lazy[800005];

	void init(int i = 1, int L = 0, int R = n - 1)
	{
		seg[i].S = L;
		if (L == R)
			return;
		int mid = (L + R) / 2;
		init(i << 1, L, mid);
		init(i << 1 | 1, mid + 1, R);
	}

	void modify(int mL, int mR, ll val, int i = 1, int L = 0, int R = n - 1)
	{
		if (mL <= L && R <= mR)
		{
			lazy[i] += val;
			seg[i].F += val;
		}
		else if (R < mL || mR < L)
			return;
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			modify(mL, mR, val, i << 1, L, mid);
			modify(mL, mR, val, i << 1 | 1, mid + 1, R);
			seg[i] = min(seg[i << 1], seg[i << 1 | 1]);
		}
	}

	pll query(int qL, int qR, int i = 1, int L = 0, int R = n - 1)
	{
		if (qL <= L && R <= qR)
			return seg[i];
		else if (R < qL || qR < L)
			return pll(1e9, n + 1);
		else
		{
			int mid = (L + R) / 2;
			lazy[i << 1] += lazy[i];
			lazy[i << 1 | 1] += lazy[i];
			seg[i << 1].F += lazy[i];
			seg[i << 1 | 1].F += lazy[i];
			lazy[i] = 0;
			return min(query(qL, qR, i << 1, L, mid),
					   query(qL, qR, i << 1 | 1, mid + 1, R));
		}
	}
	void safe_modify(int l, int r, ll val)
	{
		if (l <= r)
			modify(l, r, val);
		else
		{
			modify(l, n - 1, val);
			modify(0, r, val);
		}
	}
} seg, zero;

const ll inf = 1e9;

void init(int k, vector<int> r)
{
	n = r.size();
	seg.init();
	zero.init();
	for (int i = 0; i < n; i++)
	{
		r[i] = k - 1 - r[i];
		seg.modify(i, i, r[i]);
		zero.modify(i, i, r[i]);
	}
	for (int it = 1; it <= n; it++)
	{
		{
			auto [v, p] = zero.query(0, n - 1);
			while (v == 0)
			{
				seg.safe_modify(p + 1, (p + k - 1) % n, inf);
				zero.modify(p, p, inf);
				tie(v, p) = zero.query(0, n - 1);
			}
		}
		int cur = seg.query(0, n - 1).S;
		// cerr << cur << '\n';
		seg.modify(cur, cur, inf);
		seg.safe_modify(cur + 1, (cur + k - 1) % n, -inf);
		zero.safe_modify((cur - k + 1) % n, cur, -1);
		assert(order[cur] == 0);
		order[cur] = it;
	}
	return;
}

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 14.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 25332 KB Output is correct
2 Runtime error 31 ms 51276 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

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

Subtask #6
0 / 15.0

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

Subtask #7
0 / 25.0

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