oj.uz

Submission #748606

# Submission time Handle Problem Language Result Execution time Memory
748606 2023-05-26T14:57:28 Z alex_2008 Radio Towers (IOI22_towers) C++17
17 / 100
 1393 ms 185756 KB 
#include "towers.h"
#include <iostream>
#include <vector>
#include <cmath>
#include <set>
#include <algorithm>
using namespace std;
int ind = -1;
bool ch = true;
vector <int> h;
const int N = 100100, M = 20;
struct Node {
	int val;
	int left;
	int right;
	Node* ls;
	Node* rs;
};
Node* roots[N];
int tree[4 * N], maxim[4 * N], minim[4 * N], mx[N][M], LS[N], RS[N];
int tree2[4 * N], maxim2[4 * N], minim2[4 * N];
int minnumber = 2e9, answer_for_another_tree = 0, maxnumber = 0;
void build_another_tree(int v, int tl, int tr) {
	if (tl == tr) {
		maxim[v] = h[tl];
		minim[v] = h[tl];
		tree[v] = 0;
	}
	else {
		int tm = (tl + tr) / 2;
		build_another_tree(2 * v, tl, tm);
		build_another_tree(2 * v + 1, tm + 1, tr);
		maxim[v] = max({ maxim[2 * v], maxim[2 * v + 1] });
		minim[v] = min({ minim[2 * v], minim[2 * v + 1] });
		tree[v] = max({ tree[2 * v], tree[2 * v + 1], maxim[2 * v + 1] - minim[2 * v] });
	}
}
void query_in_another_tree(int v, int tl, int tr, int l, int r) {
	if (tr < l || tl > r) return;
	if (tl >= l && tr <= r) {
		answer_for_another_tree = max({ answer_for_another_tree, tree[v], maxim[v] - minnumber});
		minnumber = min(minnumber, minim[v]);
		return;
	}
	int tm = (tl + tr) / 2;
	query_in_another_tree(2 * v, tl, tm, l, r);
	query_in_another_tree(2 * v + 1, tm + 1, tr, l, r);
}
void build_another_tree2(int v, int tl, int tr) {
	if (tl == tr) {
		maxim2[v] = h[tl];
		minim2[v] = h[tl];
		tree2[v] = 0;
	}
	else {
		int tm = (tl + tr) / 2;
		build_another_tree2(2 * v, tl, tm);
		build_another_tree2(2 * v + 1, tm + 1, tr);
		maxim2[v] = max({ maxim2[2 * v], maxim2[2 * v + 1] });
		minim2[v] = min({ minim2[2 * v], minim2[2 * v + 1] });
		tree2[v] = max({ tree2[2 * v], tree2[2 * v + 1], maxim2[2 * v] - minim2[2 * v + 1] });
	}
}
void query_in_another_tree2(int v, int tl, int tr, int l, int r) {
	if (tr < l || tl > r) return;
	if (tl >= l && tr <= r) {
		answer_for_another_tree = max({ answer_for_another_tree, tree2[v], maxnumber - minim2[v] });
		maxnumber = max(maxnumber, maxim2[v]);
		return;
	}
	int tm = (tl + tr) / 2;
	query_in_another_tree2(2 * v, tl, tm, l, r);
	query_in_another_tree2(2 * v + 1, tm + 1, tr, l, r);
}
void build_tree(Node* v) {
	if (v->left == v->right) {
		v->val = 1;
		return;
	}
	else {
		int tm = (v->left + v->right) / 2;
		Node* ls = new Node{ 0, v->left, tm, nullptr, nullptr };
		Node* rs = new Node{ 0, tm + 1, v->right, nullptr, nullptr };
		build_tree(ls);
		build_tree(rs);
		v->ls = ls;
		v->rs = rs;
		v->val = ls->val + rs->val;
	}
}
void update(Node* old, Node* neww, int pos) {
	*neww = *old;
	if (neww->left > pos || neww->right < pos) return;
	if (neww->left == neww->right) {
		neww->val = 0;
		return;
	}
	int tm = (neww->left + neww->right) / 2;
	Node* ls = new Node{ 0, neww->left, tm, nullptr, nullptr };
	Node* rs = new Node{ 0, tm + 1, neww->right, nullptr, nullptr };
	update(old->ls, ls, pos);
	update(old->rs, rs, pos);
	neww->ls = ls;
	neww->rs = rs;
	neww->val = ls->val + rs->val;
}
int ql = 2e9, qr = -1;
void query1(Node* v, int l) {
	if (v->right < l) return;
	if (v->left >= l) {
		if (v->val > 0) {
			while (v->left != v->right) {
				if (v->ls->val > 0) {
					v = v->ls;
				}
				else v = v->rs;
			}
			ql = min(ql, v->left);
		}
		return;
	}
	query1(v->ls, l);
	query1(v->rs, l);
}
void query2(Node* v, int r) {
	if (v->left > r) return;
	if (v->right <= r) {
		if (v->val > 0) {
			while (v->left != v->right) {
				if (v->rs->val > 0) {
					v = v->rs;
				}
				else v = v->ls;
			}
			qr = max(qr, v->left);
		}
		return;
	}
	query2(v->ls, r);
	query2(v->rs, r);
}
int query3(Node* v, int l, int r) {
	if (v->left > r || v->right < l) return 0;
	if (v->left >= l && v->right <= r) return v->val;
	return query3(v->ls, l, r) +
		query3(v->rs, l, r);
}
vector <pair<int, int>> esim;
int findmaxinrange(int L, int R) {
	if (L > R) return 0;
	int u = log2(R - L + 1);
	return max(mx[L][u], mx[R - (1 << u) + 1][u]);
}
void init(int n, vector<int> a) {
	ch = true;
	h = a;
	LS[0] = -1;
	RS[n - 1] = -1;
	for (int i = 1; i < n; i++) {
		int v = i - 1;
		while (v != -1 && a[i] < a[v]) {
			v = LS[v];
		}
		LS[i] = v;
	}
	for (int i = n - 2; i >= 0; i--) {
		int v = i + 1;
		while (v != -1 && a[i] < a[v]) {
			v = RS[v];
		}
		RS[i] = v;
	}
	for (int i = 0; i < n; i++) {
		mx[i][0] = a[i];
	}
	for (int j = 1; j < 20; j++) {
		for (int i = n - 1; i >= 0; i--) {
			mx[i][j] = max(mx[i][j - 1], mx[min(n - 1, i + (1 << (j - 1)))][j - 1]);
		}
	}
	for (int i = 0; i < n; i++) {
		int hmn = 2e9;
		if (LS[i] != -1) {
			hmn = min(hmn, findmaxinrange(LS[i] + 1, i - 1));
		}
		if (RS[i] != -1) {
			hmn = min(hmn, findmaxinrange(i + 1, RS[i] - 1));
		}
		int u = hmn - a[i];
		esim.push_back({ u, i });
	}
	sort(esim.begin(), esim.end());
	roots[0] = new Node{ 0, 0, n - 1, nullptr, nullptr };
	build_tree(roots[0]);
	for (int i = 1; i < n; i++) {
		roots[i] = new Node{ 0, 0, n - 1, nullptr, nullptr };
		update(roots[i - 1], roots[i], esim[i - 1].second);
	}
	build_another_tree(1, 0, n - 1);
}
int max_towers(int L, int R, int D) {
	int n = (int)h.size();
	int left = 0, right = n - 1, answ = -1;
	while (left <= right) {
		int mid = (left + right) / 2;
		if (esim[mid].first >= D) {
			answ = mid;
			right = mid - 1;
		}
		else left = mid + 1;
	}
	if (answ == -1) return 1;
	int ans = query3(roots[answ], L, R);
	ql = 2e9;
	qr = -1;
	query1(roots[answ], L);
	query2(roots[answ], R);
	minnumber = 2e9;
	answer_for_another_tree = 0;
	if (ql != 2e9) {
		int left = L, right = ql - 1, r__ = -1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (findmaxinrange(mid, ql) - h[ql] >= D) {
				r__ = mid;
				left = mid + 1;
			}
			else right = mid - 1;
		}
		if (r__ != -1) {
			query_in_another_tree(1, 0, n - 1, L, r__);
			if (answer_for_another_tree >= D) ++ans;
		}
	}
	maxnumber = 0;
	answer_for_another_tree = 0;
	if (qr != -1) {
		int left = qr + 1, right = R, r__ = -1;
		while (left <= right) {
			int mid = (left + right) / 2;
			if (findmaxinrange(qr, mid) - h[qr] >= D) {
				r__ = mid;
				right = mid - 1;
			}
			else left = mid + 1;
		}
		if (r__ != -1) {
			query_in_another_tree2(1, 0, n - 1, r__, R);
			if (answer_for_another_tree >= D) ++ans;
		}
	}
	if (ans == 0) ++ans;
	return ans;
	//query left = INF, query right = -1
/*
7 1
10 20 60 40 50 30 70
1 5 10
*/
/*auto it = lower_bound(indexes.begin(), indexes.end(), L);
int ans = upper_bound(indexes.begin(), indexes.end(), R) - lower_bound(indexes.begin(), indexes.end(), L);
if (it != indexes.end()) {
	int q = Left[*it];
	if (L < q) {
		if (findmininrange(L, q - 1, 2) < *it) {
			++ans;
		}
	}
}
it = upper_bound(indexes.begin(), indexes.end(), R);
if (it != indexes.begin()) {
	--it;
	int q = Right[*it];
	if (q < R) {
		if (findmininrange(q + 1, R, 1) > *it) {
			++ans;
		}
	}
}
if (ans == 0) ++ans;*/
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 860 ms 106068 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 3 ms 2896 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct
4 Correct 3 ms 2896 KB Output is correct
5 Correct 3 ms 2896 KB Output is correct
6 Correct 5 ms 2904 KB Output is correct
7 Correct 4 ms 2896 KB Output is correct
8 Correct 3 ms 2896 KB Output is correct
9 Correct 3 ms 2896 KB Output is correct
10 Correct 3 ms 2896 KB Output is correct
11 Correct 3 ms 2896 KB Output is correct
12 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 3 ms 2896 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct
4 Correct 3 ms 2896 KB Output is correct
5 Correct 3 ms 2896 KB Output is correct
6 Correct 5 ms 2904 KB Output is correct
7 Correct 4 ms 2896 KB Output is correct
8 Correct 3 ms 2896 KB Output is correct
9 Correct 3 ms 2896 KB Output is correct
10 Correct 3 ms 2896 KB Output is correct
11 Correct 3 ms 2896 KB Output is correct
12 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1393 ms 184236 KB 1st lines differ - on the 1st token, expected: '11903', found: '11902'
2 Halted 0 ms 0 KB -

Subtask #5
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 356 ms 39880 KB Output is correct
2 Correct 1340 ms 185548 KB Output is correct
3 Correct 1258 ms 185540 KB Output is correct
4 Correct 1132 ms 185532 KB Output is correct
5 Correct 1216 ms 185612 KB Output is correct
6 Correct 1314 ms 185512 KB Output is correct
7 Correct 1283 ms 185756 KB Output is correct
8 Correct 1097 ms 185532 KB Output is correct
9 Correct 1145 ms 185504 KB Output is correct
10 Correct 1216 ms 185600 KB Output is correct
11 Correct 1194 ms 185572 KB Output is correct
12 Correct 231 ms 185624 KB Output is correct
13 Correct 234 ms 185504 KB Output is correct
14 Correct 238 ms 185556 KB Output is correct
15 Correct 186 ms 185584 KB Output is correct
16 Correct 193 ms 185576 KB Output is correct
17 Correct 219 ms 178916 KB Output is correct
18 Correct 240 ms 185496 KB Output is correct
19 Correct 242 ms 185604 KB Output is correct
20 Correct 233 ms 185492 KB Output is correct
21 Correct 235 ms 185532 KB Output is correct
22 Correct 231 ms 185532 KB Output is correct
23 Correct 242 ms 185656 KB Output is correct
24 Correct 195 ms 185532 KB Output is correct
25 Correct 187 ms 185500 KB Output is correct
26 Correct 197 ms 185492 KB Output is correct
27 Correct 184 ms 185568 KB Output is correct
28 Correct 3 ms 2896 KB Output is correct
29 Correct 3 ms 2896 KB Output is correct
30 Correct 3 ms 2896 KB Output is correct
31 Correct 3 ms 2896 KB Output is correct
32 Correct 5 ms 2896 KB Output is correct
33 Correct 2 ms 1360 KB Output is correct
34 Correct 3 ms 2896 KB Output is correct
35 Correct 3 ms 2880 KB Output is correct
36 Correct 3 ms 2896 KB Output is correct
37 Correct 4 ms 2896 KB Output is correct
38 Correct 3 ms 2896 KB Output is correct
39 Correct 3 ms 2896 KB Output is correct
40 Correct 3 ms 2896 KB Output is correct
41 Correct 3 ms 2896 KB Output is correct
42 Correct 4 ms 2896 KB Output is correct
43 Correct 3 ms 2896 KB Output is correct

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 768 KB Output is correct
2 Correct 3 ms 2896 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct
4 Correct 3 ms 2896 KB Output is correct
5 Correct 3 ms 2896 KB Output is correct
6 Correct 5 ms 2904 KB Output is correct
7 Correct 4 ms 2896 KB Output is correct
8 Correct 3 ms 2896 KB Output is correct
9 Correct 3 ms 2896 KB Output is correct
10 Correct 3 ms 2896 KB Output is correct
11 Correct 3 ms 2896 KB Output is correct
12 Incorrect 1 ms 336 KB 1st lines differ - on the 1st token, expected: '2', found: '1'
13 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 860 ms 106068 KB 12th lines differ - on the 1st token, expected: '2', found: '1'
2 Halted 0 ms 0 KB -