oj.uz

Submission #1020105

# Submission time Handle Problem Language Result Execution time Memory
1020105 2024-07-11T14:55:03 Z j_vdd16 Comparing Plants (IOI20_plants) C++17
14 / 100
 4000 ms 9616 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 >= l && tr <= r)
			lazySub[i] = v;

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

		int tm = (tl + tr) / 2;
		range(l, r, i * 2, tl, tm);
		range(l, r, i * 2 + 1, tm, tr);
	}
	ii range(int l, int r, int i = 1, int tl = 0, int tr = -1) {
		if (tr == -1)
			tr = N;

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

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

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

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

int n;
vi r;

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

	int idx = n;
	vb vis(n);
	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;
			}
		}

		vis[low] = true;
		perm[low] = idx--;
	}
}

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 0 ms 604 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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 540 KB Output is correct
7 Correct 147 ms 5256 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 6 ms 544 KB Output is correct
10 Correct 154 ms 5216 KB Output is correct
11 Correct 155 ms 4944 KB Output is correct
12 Correct 142 ms 5204 KB Output is correct
13 Correct 150 ms 5204 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Correct 1 ms 348 KB Output is correct
6 Correct 6 ms 540 KB Output is correct
7 Correct 147 ms 5256 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 6 ms 544 KB Output is correct
10 Correct 154 ms 5216 KB Output is correct
11 Correct 155 ms 4944 KB Output is correct
12 Correct 142 ms 5204 KB Output is correct
13 Correct 150 ms 5204 KB Output is correct
14 Correct 1762 ms 5716 KB Output is correct
15 Execution timed out 4098 ms 9552 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 51 ms 4788 KB Output is correct
4 Execution timed out 4030 ms 9616 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 344 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 604 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 -