oj.uz

Submission #748574

# Submission time Handle Problem Language Result Execution time Memory
748574 2023-05-26T13:40:39 Z alex_2008 Radio Towers (IOI22_towers) C++17
17 / 100
 1406 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 minnumber = 2e9, answer_for_another_tree = 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]);
		answer_for_another_tree = max(answer_for_another_tree, 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_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);
	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 762 ms 105992 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 720 KB Output is correct
2 Correct 4 ms 2896 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct
4 Correct 4 ms 2896 KB Output is correct
5 Correct 4 ms 2896 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Incorrect 4 ms 2896 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 4 ms 2896 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct
4 Correct 4 ms 2896 KB Output is correct
5 Correct 4 ms 2896 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Incorrect 4 ms 2896 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1312 ms 184160 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 280 ms 39964 KB Output is correct
2 Correct 1406 ms 185580 KB Output is correct
3 Correct 1058 ms 185500 KB Output is correct
4 Correct 1320 ms 185480 KB Output is correct
5 Correct 1116 ms 185472 KB Output is correct
6 Correct 1172 ms 185560 KB Output is correct
7 Correct 975 ms 185644 KB Output is correct
8 Correct 1002 ms 185524 KB Output is correct
9 Correct 1032 ms 185544 KB Output is correct
10 Correct 817 ms 185484 KB Output is correct
11 Correct 1046 ms 185572 KB Output is correct
12 Correct 269 ms 185652 KB Output is correct
13 Correct 255 ms 185484 KB Output is correct
14 Correct 258 ms 185496 KB Output is correct
15 Correct 196 ms 185564 KB Output is correct
16 Correct 207 ms 185476 KB Output is correct
17 Correct 232 ms 178964 KB Output is correct
18 Correct 240 ms 185544 KB Output is correct
19 Correct 245 ms 185496 KB Output is correct
20 Correct 253 ms 185664 KB Output is correct
21 Correct 243 ms 185496 KB Output is correct
22 Correct 259 ms 185492 KB Output is correct
23 Correct 252 ms 185756 KB Output is correct
24 Correct 232 ms 185500 KB Output is correct
25 Correct 186 ms 185560 KB Output is correct
26 Correct 209 ms 185560 KB Output is correct
27 Correct 202 ms 185496 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 4 ms 2852 KB Output is correct
32 Correct 3 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 4 ms 3024 KB Output is correct
36 Correct 3 ms 2896 KB Output is correct
37 Correct 5 ms 2840 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 3 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 720 KB Output is correct
2 Correct 4 ms 2896 KB Output is correct
3 Correct 4 ms 2896 KB Output is correct
4 Correct 4 ms 2896 KB Output is correct
5 Correct 4 ms 2896 KB Output is correct
6 Correct 4 ms 2896 KB Output is correct
7 Incorrect 4 ms 2896 KB 1st lines differ - on the 1st token, expected: '34', found: '33'
8 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

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