oj.uz

Submission #825271

# Submission time Handle Problem Language Result Execution time Memory
825271 2023-08-14T16:32:59 Z thimote75 Comparing Plants (IOI20_plants) C++14
100 / 100
 1745 ms 199452 KB 
#include "plants.h"
#include <bits/stdc++.h>
#define int long long

using namespace std;

using idata = vector<int>;
using igrid = vector<idata>;
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;
igrid lw2k, rw2k;
igrid ld2k, rd2k;
const int MAXK = 20;

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

	if (a == -1) return 1e9;

	return min(b - a, N + a - b);
}
void blfi (igrid &g, igrid &d, idata &v) {
	g.resize(v.size(), idata(MAXK, -1));
	d.resize(v.size(), idata(MAXK, 1e9));
	for (int i = 0; i < v.size(); i ++) {
		g[i][0] = v[i];
		d[i][0] = distance(v[i], i);
	}
	
	for (int k = 0; k + 1 < MAXK; k ++) {
		for (int i = 0; i < v.size(); i ++) {
			if (g[i][k] == -1) continue ;

			g[i][k + 1] = g[g[i][k]][k];
			d[i][k + 1] = d[i][k] + d[g[i][k]][k];
		}
	}
}

void init(signed k, vector<signed> r) {
	K = k;

	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 } );
	}

	blfi (lw2k, ld2k, lw);
	blfi (rw2k, rd2k, rw);

	return;
}

bool dfs (igrid &V, igrid &D, int s, int t, int dist_max) {
	int ct = 0;

	for (int k = MAXK - 1; k >= 0; k --) {
		if (ct + D[s][k] > dist_max || V[s][k] == -1) continue ;
		dbg(s, t, k, ct, dist_max, V[s][k], D[s][k]);

		ct += D[s][k];
		s   = V[s][k];
	}

	return distance(s, t) < K && A[s] >= A[t];
}
bool dfs (int s, int t) {
	return dfs(lw2k, ld2k, s, t, t > s ? N - t + s : s - t)
	    || dfs(rw2k, rd2k, s, t, t < s ? N - s + t : t - s);
}
 
signed compare_plants(signed x, signed 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&, long long int)':
plants.cpp:50:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |  for (int i = count; i < r.size(); i ++)
      |                      ~~^~~~~~~~~~
plants.cpp: In function 'void blfi(igrid&, igrid&, idata&)':
plants.cpp:229:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  229 |  for (int i = 0; i < v.size(); i ++) {
      |                  ~~^~~~~~~~~~
plants.cpp:235:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  235 |   for (int i = 0; i < v.size(); i ++) {
      |                   ~~^~~~~~~~~~
plants.cpp: In function 'void init(int, std::vector<int>)':
plants.cpp:251:6: warning: unused variable 's' [-Wunused-variable]
  251 |  int s = 0;
      |      ^

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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 54 ms 3044 KB Output is correct
7 Correct 191 ms 22700 KB Output is correct
8 Correct 624 ms 195700 KB Output is correct
9 Correct 738 ms 195756 KB Output is correct
10 Correct 788 ms 195776 KB Output is correct
11 Correct 931 ms 195680 KB Output is correct
12 Correct 999 ms 195772 KB Output is correct
13 Correct 1068 ms 195756 KB Output is correct
14 Correct 1063 ms 195648 KB Output is correct

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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 100 ms 7544 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 4 ms 1236 KB Output is correct
10 Correct 95 ms 7540 KB Output is correct
11 Correct 117 ms 7656 KB Output is correct
12 Correct 122 ms 7544 KB Output is correct
13 Correct 91 ms 7544 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 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 5 ms 1236 KB Output is correct
7 Correct 100 ms 7544 KB Output is correct
8 Correct 3 ms 340 KB Output is correct
9 Correct 4 ms 1236 KB Output is correct
10 Correct 95 ms 7540 KB Output is correct
11 Correct 117 ms 7656 KB Output is correct
12 Correct 122 ms 7544 KB Output is correct
13 Correct 91 ms 7544 KB Output is correct
14 Correct 215 ms 22684 KB Output is correct
15 Correct 1433 ms 195768 KB Output is correct
16 Correct 211 ms 23976 KB Output is correct
17 Correct 1482 ms 197080 KB Output is correct
18 Correct 1141 ms 197064 KB Output is correct
19 Correct 1298 ms 196952 KB Output is correct
20 Correct 1510 ms 197064 KB Output is correct

Subtask #4
17.0 / 17.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 116 ms 4796 KB Output is correct
4 Correct 1559 ms 195692 KB Output is correct
5 Correct 1467 ms 195652 KB Output is correct
6 Correct 1745 ms 195648 KB Output is correct
7 Correct 1683 ms 195648 KB Output is correct
8 Correct 1563 ms 195776 KB Output is correct
9 Correct 1339 ms 198776 KB Output is correct
10 Correct 1252 ms 198792 KB Output is correct
11 Correct 1135 ms 198556 KB Output is correct
12 Correct 1075 ms 198748 KB Output is correct
13 Correct 1102 ms 198824 KB Output is correct

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 1 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 16 ms 1184 KB Output is correct
8 Correct 14 ms 1140 KB Output is correct
9 Correct 18 ms 1156 KB Output is correct
10 Correct 14 ms 1236 KB Output is correct
11 Correct 16 ms 1136 KB Output is correct
12 Correct 17 ms 1136 KB Output is correct
13 Correct 14 ms 1144 KB Output is correct

Subtask #6
15.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 1236 KB Output is correct
6 Correct 816 ms 195776 KB Output is correct
7 Correct 926 ms 195768 KB Output is correct
8 Correct 1176 ms 195772 KB Output is correct
9 Correct 1169 ms 195768 KB Output is correct
10 Correct 855 ms 197932 KB Output is correct
11 Correct 983 ms 198544 KB Output is correct
12 Correct 958 ms 197828 KB Output is correct
13 Correct 988 ms 197904 KB Output is correct
14 Correct 1218 ms 198128 KB Output is correct
15 Correct 1254 ms 198384 KB Output is correct
16 Correct 929 ms 197860 KB Output is correct
17 Correct 846 ms 198028 KB Output is correct

Subtask #7
25.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 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 54 ms 3044 KB Output is correct
7 Correct 191 ms 22700 KB Output is correct
8 Correct 624 ms 195700 KB Output is correct
9 Correct 738 ms 195756 KB Output is correct
10 Correct 788 ms 195776 KB Output is correct
11 Correct 931 ms 195680 KB Output is correct
12 Correct 999 ms 195772 KB Output is correct
13 Correct 1068 ms 195756 KB Output is correct
14 Correct 1063 ms 195648 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 1236 KB Output is correct
21 Correct 100 ms 7544 KB Output is correct
22 Correct 3 ms 340 KB Output is correct
23 Correct 4 ms 1236 KB Output is correct
24 Correct 95 ms 7540 KB Output is correct
25 Correct 117 ms 7656 KB Output is correct
26 Correct 122 ms 7544 KB Output is correct
27 Correct 91 ms 7544 KB Output is correct
28 Correct 215 ms 22684 KB Output is correct
29 Correct 1433 ms 195768 KB Output is correct
30 Correct 211 ms 23976 KB Output is correct
31 Correct 1482 ms 197080 KB Output is correct
32 Correct 1141 ms 197064 KB Output is correct
33 Correct 1298 ms 196952 KB Output is correct
34 Correct 1510 ms 197064 KB Output is correct
35 Correct 0 ms 212 KB Output is correct
36 Correct 1 ms 212 KB Output is correct
37 Correct 116 ms 4796 KB Output is correct
38 Correct 1559 ms 195692 KB Output is correct
39 Correct 1467 ms 195652 KB Output is correct
40 Correct 1745 ms 195648 KB Output is correct
41 Correct 1683 ms 195648 KB Output is correct
42 Correct 1563 ms 195776 KB Output is correct
43 Correct 1339 ms 198776 KB Output is correct
44 Correct 1252 ms 198792 KB Output is correct
45 Correct 1135 ms 198556 KB Output is correct
46 Correct 1075 ms 198748 KB Output is correct
47 Correct 1102 ms 198824 KB Output is correct
48 Correct 0 ms 212 KB Output is correct
49 Correct 0 ms 212 KB Output is correct
50 Correct 0 ms 212 KB Output is correct
51 Correct 1 ms 212 KB Output is correct
52 Correct 1 ms 212 KB Output is correct
53 Correct 2 ms 340 KB Output is correct
54 Correct 16 ms 1184 KB Output is correct
55 Correct 14 ms 1140 KB Output is correct
56 Correct 18 ms 1156 KB Output is correct
57 Correct 14 ms 1236 KB Output is correct
58 Correct 16 ms 1136 KB Output is correct
59 Correct 17 ms 1136 KB Output is correct
60 Correct 14 ms 1144 KB Output is correct
61 Correct 110 ms 6436 KB Output is correct
62 Correct 276 ms 24868 KB Output is correct
63 Correct 976 ms 198556 KB Output is correct
64 Correct 1350 ms 198860 KB Output is correct
65 Correct 1596 ms 199052 KB Output is correct
66 Correct 1525 ms 199248 KB Output is correct
67 Correct 1465 ms 199452 KB Output is correct
68 Correct 1148 ms 198712 KB Output is correct
69 Correct 1391 ms 199404 KB Output is correct
70 Correct 1311 ms 198612 KB Output is correct
71 Correct 1592 ms 198884 KB Output is correct
72 Correct 1676 ms 199048 KB Output is correct
73 Correct 1596 ms 199124 KB Output is correct
74 Correct 1026 ms 198752 KB Output is correct
75 Correct 1224 ms 198912 KB Output is correct