oj.uz

Submission #832521

# Submission time Handle Problem Language Result Execution time Memory
832521 2023-08-21T11:05:45 Z Johann Comparing Plants (IOI20_plants) C++14
0 / 100
 1 ms 468 KB 
#include "plants.h"
#include "bits/stdc++.h"
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int, int> pii;
typedef vector<pii> vpii;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()

pii operator+(const pii &a, const pii &b)
{
	return {a.first + b.first, a.second + b.second};
}

const int INF = 1 << 30;
int N, K;
vi A;

struct segtree
{
	int size;
	vpii arr;
	vi op;
	void init(vi &R)
	{
		size = 1;
		while (size < sz(R))
			size *= 2;
		arr.assign(2 * size, {0, 0});
		op.assign(2 * size, 0);
		for (int i = 0; i < sz(R); ++i)
			arr[i + size] = {R[i], i};
		for (int i = size - 1; i > 0; --i)
			arr[i] = min(arr[2 * i], arr[2 * i + 1]);
	}
	void propagate(int x)
	{
		if (x < size)
		{
			op[2 * x] += op[x];
			op[2 * x + 1] += op[x];
		}
		arr[x] = arr[x] + make_pair(op[x], 0);
		op[x] = 0;
	}
	void set(int i, int v)
	{
		i += size;
		arr[i] = {v, i - size};
		while ((i >>= 1) > 0)
			arr[i] = min(arr[2 * i], arr[2 * i + 1]) + make_pair(op[i], 0);
	}
	void add(int l, int r, int v)
	{
		if (l < 0)
			add(l + N, N, v, 1, 0, size);
		add(max(l, 0), r, v, 1, 0, size);
	}
	void add(int l, int r, int v, int x, int lx, int rx)
	{
		if (l <= lx && rx <= r)
		{
			op[x] += v;
			propagate(x);
			return;
		}
		if (r <= lx || rx <= l)
			return;
		propagate(x);
		int m = (lx + rx) / 2;
		add(l, r, v, 2 * x, lx, m);
		add(l, r, v, 2 * x + 1, m, rx);
		arr[x] = min(arr[2 * x], arr[2 * x + 1]);
	}
	pii query(int l, int r)
	{
		pii left = {INF, -1};
		if (l < 0)
			left = query(l + N, N, 1, 0, size);
		pii right = query(max(l, 0), r, 1, 0, size);
		if (left.first == right.first)
			return left;
		else
			return min(left, right);
	}
	pii query(int l, int r, int x, int lx, int rx)
	{
		propagate(x);
		if (l <= lx && rx <= r)
			return arr[x];
		if (r <= lx || rx <= l)
			return {INF, -1};
		int m = (lx + rx) / 2;
		return min(query(l, r, 2 * x, lx, m), query(l, r, 2 * x + 1, m, rx));
	}
};
segtree seg;

void init(int _K, std::vector<int> r)
{
	K = _K;
	N = sz(r);
	A.assign(N, -1);
	seg.init(r);
	for (int i = N; i > 0; --i)
	{
		pii cand = seg.query(0, N);
		assert(cand.first == 0);
		int idx = seg.query(cand.second - K + 1, cand.second + 1).second;
		assert(idx != -1 && A[idx] == -1);
		A[idx] = i;
		seg.set(idx, INF);
		seg.add(idx - K + 1, idx, -1);
	}
	return;
}

int compare_plants(int x, int y)
{
	return (A[x] > A[y]) ? 1 : -1;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 272 KB Output is correct
4 Runtime error 1 ms 340 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Runtime error 1 ms 468 KB Execution killed with signal 6
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 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 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Incorrect 0 ms 212 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Runtime error 1 ms 352 KB Execution killed with signal 6
4 Halted 0 ms 0 KB -

Subtask #7
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 272 KB Output is correct
4 Runtime error 1 ms 340 KB Execution killed with signal 6
5 Halted 0 ms 0 KB -