oj.uz

Submission #769239

# Submission time Handle Problem Language Result Execution time Memory
769239 2023-06-29T10:25:49 Z marvinthang Comparing Plants (IOI20_plants) C++17
5 / 100
 517 ms 50492 KB 
/*************************************
*    author: marvinthang             *
*    created: 29.06.2023 15:49:29    *
*************************************/

#include "plants.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }

// end of template

int N, K;
vector <vector <bool>> visited;
vector <vector<int>> st_left, st_right;
vector <int> st, lazy, h;

int get_prev(int i, int j) {
	i -= j;
	return i < 0 ? i + N : i;
}

int get_next(int i, int j) {
	i += j;
	return i >= N ? i - N : i;
}

void build(int i, int l, int r, vector <int> &v) {
	if (r - l == 1) {
		st[i] = v[l];
		return;
	}
	int m = l + r >> 1;
	build(i << 1, l, m, v);
	build(i << 1 | 1, m, r, v);
	st[i] = min(st[i << 1], st[i << 1 | 1]);
}

void pushDown(int i) {
	if (!lazy[i]) return;
	st[i << 1] += lazy[i];
	lazy[i << 1] += lazy[i];
	st[i << 1 | 1] += lazy[i];
	lazy[i << 1 | 1] += lazy[i];
	lazy[i] = 0;
}

int find_zero(void) {
	int i = 1, l = 0, r = N;
	while (true) {
		if (r - l == 1) return l;
		pushDown(i);
		int m = l + r >> 1;
		if (!st[i << 1]) i = i << 1, r = m;
		else i = i << 1 | 1, l = m;
	}
	return -1;
}

void update(int i, int l, int r, int u, int v, int add) {
	if (l >= v || r <= u) return;
	if (u <= l && r <= v) {
		st[i] += add;
		lazy[i] += add;
		return;
	}
	pushDown(i);
	int m = l + r >> 1;
	update(i << 1, l, m, u, v, add);
	update(i << 1 | 1, m, r, u, v, add);
	st[i] = min(st[i << 1], st[i << 1 | 1]);
}

int dist(int i, int j) {
	return i < j ? j - i : j + N - i;
}

void init(int k, vector <int> r) {
	K = k; --K;
	N = r.size();
	st.resize(N * 4 + 23);
	lazy.resize(N * 4 + 23);
	build(1, 0, N, r);
	h.resize(N);
	vector <vector <int>> adj(N);
	set <int> pos_zero, good_zero;
	REPD(v, N) {
		while (!st[1]) {
			int p = find_zero();
			update(1, 0, N, p, p + 1, 1e9);
			auto it = pos_zero.insert(p).fi;
			if (pos_zero.size() == 1) {
				good_zero.insert(p);
				continue;
			}
			int prv = it == pos_zero.begin() ? *pos_zero.rbegin() : *prev(it);
			int nxt = next(it) == pos_zero.end() ? *pos_zero.begin() : *next(it);
			if (dist(prv, p) > K) good_zero.insert(p);
			if (dist(p, nxt) <= K) good_zero.erase(nxt);
		}
		int i = *good_zero.begin();
		good_zero.erase(good_zero.begin());
		auto it = pos_zero.find(i);
		int prv = it == pos_zero.begin() ? *pos_zero.rbegin() : *prev(it);
		int nxt = next(it) == pos_zero.end() ? *pos_zero.begin() : *next(it);
		pos_zero.erase(it);
		if (!pos_zero.empty() && dist(prv, nxt) > K) good_zero.insert(nxt);

		h[i] = v;
		prv = get_prev(i, K);
		if (prv < i) update(1, 0, N, prv, i, -1);
		else {
			update(1, 0, N, prv, N, -1);
			update(1, 0, N, 0, i, -1);
		}
	}
	set <pair <int, int>> left, right;
	REP(i, K) {
		int x = get_prev(0, i + 1);
		left.insert(make_pair(h[x], x));
		x = get_next(0, i + 1);
		right.insert(make_pair(h[x], x));
	}
	st_left.push_back(vector<int>(N, -1));
	st_right.push_back(vector<int>(N, -1));
	REP(i, N) {
		auto it = left.lower_bound(make_pair(h[i], i));
		if (it != left.begin()) st_left[0][i] = prev(it)->se;
		it = right.lower_bound(make_pair(h[i], i));
		if (it != right.begin()) st_right[0][i] = prev(it)->se;
		int x = get_prev(i, K);
		left.erase(make_pair(h[x], x));
		left.insert(make_pair(h[i], i));

		x = get_next(i, 1);
		right.erase(make_pair(h[x], x));
		x = get_next(i, K + 1);
		right.insert(make_pair(h[x], x));
	}

	for (int k = 1; MASK(k) <= N; ++k) {
		vector <int> nl, nr;
		REP(i, N) {
			nl.push_back(~st_left.back()[i] ? st_left.back()[st_left.back()[i]] : -1);
			nr.push_back(~st_right.back()[i] ? st_right.back()[st_right.back()[i]] : -1);
		}
		st_left.push_back(nl);
		st_right.push_back(nr);
	}
}

int compare_plants(int x, int y) {
	int v = 1;
	if (x > y) {
		v = -1;
		swap(x, y);
	}
	int u = x;
	REPD(i, st_right.size()) {
		int v = st_right[i][u];
		if (~v && u < v && v <= y) u = v;
	}
	if (u == y || (dist(u, y) <= K && h[u] > h[y])) return v;
	u = x;
	REPD(i, st_left.size()) {
		int v = st_left[i][u];
		if (~v && (v < min(u, x) || v >= y)) u = v;
	}
	if (u == y || (dist(y, u) <= K && h[u] > h[y])) return v;
	u = y;
	REPD(i, st_right.size()) {
		int v = st_right[i][u];
		if (~v && (v > max(u, y) || v <= x)) u = v;
	}
	if (u == x || (dist(u, x) <= K && h[u] > h[x])) return -v;
	u = y;
	REPD(i, st_left.size()) {
		int v = st_left[i][u];
		if (~v && u > v && v >= x) u = v;
	}
	if (u == x || (dist(x, u) <= K && h[u] > h[x])) return -v;
	
	return 0;
}

Compilation message

plants.cpp: In function 'void build(int, int, int, std::vector<int>&)':
plants.cpp:66:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |  int m = l + r >> 1;
      |          ~~^~~
plants.cpp: In function 'int find_zero()':
plants.cpp:86:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |   int m = l + r >> 1;
      |           ~~^~~
plants.cpp: In function 'void update(int, int, int, int, int, int)':
plants.cpp:101:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |  int m = l + r >> 1;
      |          ~~^~~

Subtask #1
5.0 / 5.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 276 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 43 ms 3080 KB Output is correct
7 Correct 87 ms 6844 KB Output is correct
8 Correct 318 ms 50280 KB Output is correct
9 Correct 350 ms 50092 KB Output is correct
10 Correct 376 ms 50064 KB Output is correct
11 Correct 402 ms 50492 KB Output is correct
12 Correct 405 ms 50008 KB Output is correct
13 Correct 297 ms 49440 KB Output is correct
14 Correct 517 ms 49456 KB Output is correct

Subtask #2
0 / 14.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 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 1 ms 212 KB Output isn't correct
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 Correct 0 ms 212 KB Output is correct
3 Incorrect 61 ms 3360 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 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 2 ms 308 KB Output is correct
7 Correct 16 ms 1256 KB Output is correct
8 Incorrect 16 ms 1208 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #6
0 / 15.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Incorrect 2 ms 468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #7
0 / 25.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 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 276 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 43 ms 3080 KB Output is correct
7 Correct 87 ms 6844 KB Output is correct
8 Correct 318 ms 50280 KB Output is correct
9 Correct 350 ms 50092 KB Output is correct
10 Correct 376 ms 50064 KB Output is correct
11 Correct 402 ms 50492 KB Output is correct
12 Correct 405 ms 50008 KB Output is correct
13 Correct 297 ms 49440 KB Output is correct
14 Correct 517 ms 49456 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Incorrect 1 ms 212 KB Output isn't correct
20 Halted 0 ms 0 KB -