oj.uz

Submission #825247

# Submission time Handle Problem Language Result Execution time Memory
825247 2023-08-14T16:12:50 Z thimote75 Comparing Plants (IOI20_plants) C++14
38 / 100
 4000 ms 25316 KB 
#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

using idata = vector<int>;
using iset  = set<int>;
using di    = pair<int, int>;

template<typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template<typename T>
string to_string (T x) {
	string S = "[";
	bool first = true;
	for (const auto v : x) {
		if (!first)  S += ", ";
		S += to_string(v);
		first = false;
	}
	S += "]";
	return S;
}
string to_string( string s) {
	return s;
}
string to_string(bool b) {
	return to_string((int) b);
}

void dbg_out () { cout << endl; }
template<typename Head, typename... Tail>
void dbg_out (Head H, Tail... T) {
	cout << to_string(H) << " ";
	dbg_out(T...);
}

#ifdef DEBUG
#  define dbg(...) { cout << "(" << #__VA_ARGS__ << "): "; dbg_out(__VA_ARGS__); }
#else
#  define dbg(...)
#endif

void shift (idata &r, int count) {
	idata h;
	for (int i = count; i < r.size(); i ++)
		h.push_back(r[i]);
	for (int i = 0; i < count; i ++)
		h.push_back(r[i]);
	
	r.swap(h);
}

idata A;

int K, N;

struct SGData {
	int min_value = 1e9;
	int first_sol = 1e9;
	int first_min = 0;
	int  last_min = 0;
	int delta     = 0;

	void merge (SGData &left, SGData &right) {
		min_value = min(left.min_value, right.min_value);

		if (left.min_value == min_value)
			first_min = left.first_min;
		else first_min = right.first_min;

		if (right.min_value == min_value)
			last_min = right.last_min;
		else last_min = left.last_min;

		first_sol = 1e9;
		if ( left.min_value == min_value) first_sol = min(first_sol,  left.first_sol);
		if (right.min_value == min_value) first_sol = min(first_sol, right.first_sol);

		if (left.min_value == min_value
		&& right.min_value == min_value
		&& right.first_min - left.last_min >= K)
			first_sol = min(first_sol, right.first_min);

		min_value += delta;
	}
	void add (int dv) {
		min_value += dv;
		delta     += dv;
	}
	int answer (int N) {
		int e0 = last_min - N;
		int dt = first_min - e0;

		if (dt >= K) return first_min;
		return first_sol;
	}
};
string to_string (SGData data) {
	return "D[[" + to_string(data.first_min) + "; " + to_string(data.last_min) + "], " + to_string(data.min_value) + " " + to_string(data.first_sol) + " " + to_string(data.delta) + "]";
}
struct SegTree {
	vector<SGData> tree;

	int size, start, height;
	SegTree (int _size) {
		size   = _size;
		height = ceil(log2(size));
		start  = 1 << height;

		tree.resize(start << 1);

		for (int i = 0; i < size; i ++) {
			tree[i + start].min_value = 0;
			tree[i + start].first_min = i;
			tree[i + start]. last_min = i;
		}

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

	void modify (int i, int value) {
		tree[i].add(value);

		while (i != 1) {
			i >>= 1;

			tree[i].merge(tree[i * 2], tree[i * 2 + 1]);
		}
	}
	void modify (int l, int r, int value) {
		l += start;
		r += start;

		while (l < r) {
			if ((l & 1) == 1) modify(l, value);
			if ((r & 1) == 0) modify(r, value);

			l = (l + 1) >> 1;
			r = (r - 1) >> 1;
		}

		if (l == r) modify(l, value);
	}
	void cmod (int l, int r, int v) {
		if (r < 0) {
			l += size;
			r += size;
		}

		if (l < 0) {
			modify(0, r, v);
			modify(l + size, size - 1, v);
		} else modify(l, r, v);
	}
	int query () {
		return tree[1].answer(size);
	}
};

template<typename T>
struct SegTreeMax {
	vector<T> tree;

	int start, size, height;
	SegTreeMax (int _size, T def) {
		size   = _size;
		height = ceil(log2(size));
		start  = 1 << height;

		tree.resize(start << 1, def);
	}

	void update (int index, T value) {
		index += start;
		tree[index] = value;

		while (index != 1) {
			index >>= 1;

			tree[index] = max(tree[index * 2], tree[index * 2 + 1]);
		}
	}
	T query (int l, int r, T def) {
		dbg(l, r, def);
		l += start;
		r += start;

		while (l < r) {
			if ((l & 1) == 1) def = max(def, tree[l]);
			if ((r & 1) == 0) def = max(def, tree[r]);
		
			l = (l + 1) >> 1;
			r = (r - 1) >> 1;
		}

		if (l == r) def = max(def, tree[l]);
		return def;
	}
	T cquery (int l, int r, T def) {
		if (l < 0)
			return max(query(0, r, def), query(l + size, size - 1, def));
		if (r >= size)
			return max(query(0, r - size, def), query(l, size - 1, def));
		return query(l, r, def);
	}
};

idata lw, rw;

void init(int k, idata r) {
	K = k;
 
	idata r0 = r;
	int n = r.size(); N = n;
 
	A.resize(n);
 
	int s = 0;
 
	SegTree tree(n);
	for (int i = 0; i < n; i ++) tree.modify(i, i, r[i]);
	dbg(tree.tree);
 
	for (int v = n - 1; v >= 0; v --) {
		int p = tree.query();
 
		dbg(p);
 
		tree.modify(p, p, 1e9);
		
		int l = p - k + 1;
		int r = p - 1;
 
		tree.cmod(l, r, -1);
	
		A[p] = v;
		dbg(tree.tree);
	}

	idata AA(N);
	for (int i = 0; i < N; i ++)
		AA[A[i]] = i;

	lw.resize(N, -1);
	rw.resize(N, -1);

	di def = { -1e9, -1 };
	SegTreeMax<di> maxTree(N, def);
 
	for (int i = 0; i < N; i ++) {
		int j = AA[i];
		lw[j] = maxTree.cquery( j - K + 1, j - 1, def ).second;
		rw[j] = maxTree.cquery( j + 1, j - 1 + K, def ).second;

		maxTree.update( j, { i, j } );
	}

	dbg(lw);
	dbg(rw);

	return;
}

int distance (int a, int b) {
	if (a > b) swap(a, b);

	return min(b - a, N + a - b);
}
bool dfs (idata &V, int s, int t) {
	if (s == -1) return false;
	if (distance(s, t) < K)
		return A[s] > A[t];
	return dfs(V, V[s], t);
}
bool dfs (int s, int t) {
	return dfs(lw, s, t) || dfs(rw, s, t);
}
 
int compare_plants(int x, int y) {
	bool hx = dfs(x, y);
	bool hy = dfs(y, x);
	if (hx == hy) return 0;

	if (hx) return 1;
	return -1;
}

Compilation message

plants.cpp: In function 'void shift(idata&, int)':
plants.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |  for (int i = count; i < r.size(); i ++)
      |                      ~~^~~~~~~~~~
plants.cpp: In function 'void init(int, idata)':
plants.cpp:222:6: warning: unused variable 's' [-Wunused-variable]
  222 |  int s = 0;
      |      ^

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 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 46 ms 3020 KB Output is correct
7 Correct 136 ms 4920 KB Output is correct
8 Correct 172 ms 22448 KB Output is correct
9 Correct 240 ms 22476 KB Output is correct
10 Correct 813 ms 22508 KB Output is correct
11 Execution timed out 4067 ms 22476 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #2
14.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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 51 ms 3228 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 51 ms 3240 KB Output is correct
11 Correct 46 ms 3148 KB Output is correct
12 Correct 48 ms 3372 KB Output is correct
13 Correct 51 ms 3256 KB Output is correct

Subtask #3
13.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 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 51 ms 3228 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 3 ms 340 KB Output is correct
10 Correct 51 ms 3240 KB Output is correct
11 Correct 46 ms 3148 KB Output is correct
12 Correct 48 ms 3372 KB Output is correct
13 Correct 51 ms 3256 KB Output is correct
14 Correct 84 ms 4876 KB Output is correct
15 Correct 619 ms 22476 KB Output is correct
16 Correct 88 ms 4888 KB Output is correct
17 Correct 637 ms 22504 KB Output is correct
18 Correct 380 ms 22384 KB Output is correct
19 Correct 355 ms 22448 KB Output is correct
20 Correct 614 ms 22444 KB Output is correct

Subtask #4
0 / 17.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 275 ms 3284 KB Output is correct
4 Execution timed out 4064 ms 22388 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
11.0 / 11.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 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 340 KB Output is correct
7 Correct 13 ms 872 KB Output is correct
8 Correct 11 ms 856 KB Output is correct
9 Correct 19 ms 940 KB Output is correct
10 Correct 13 ms 852 KB Output is correct
11 Correct 14 ms 972 KB Output is correct
12 Correct 17 ms 1048 KB Output is correct
13 Correct 10 ms 964 KB Output is correct

Subtask #6
0 / 15.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 Correct 2 ms 340 KB Output is correct
6 Correct 523 ms 22456 KB Output is correct
7 Correct 944 ms 22448 KB Output is correct
8 Correct 622 ms 22516 KB Output is correct
9 Correct 601 ms 25316 KB Output is correct
10 Correct 1482 ms 24600 KB Output is correct
11 Correct 692 ms 25148 KB Output is correct
12 Execution timed out 4043 ms 24492 KB Time limit exceeded
13 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 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 46 ms 3020 KB Output is correct
7 Correct 136 ms 4920 KB Output is correct
8 Correct 172 ms 22448 KB Output is correct
9 Correct 240 ms 22476 KB Output is correct
10 Correct 813 ms 22508 KB Output is correct
11 Execution timed out 4067 ms 22476 KB Time limit exceeded
12 Halted 0 ms 0 KB -