oj.uz

Submission #1040844

# Submission time Handle Problem Language Result Execution time Memory
1040844 2024-08-01T10:36:58 Z 42kangaroo Radio Towers (IOI22_towers) C++17
0 / 100
 1137 ms 72544 KB 
#include "towers.h"
#include "bits/stdc++.h"

using namespace std;

struct SegTeRan {
	vector<int> a;

	int get(int l, int r, int i, int lq, int rq) {
		if (r <= lq || rq <= l) return 0;
		if (lq <= l && r <= rq) return a[i];
		int m = (l + r)/2;
		return max(get(l, m, 2*i + 1, lq, rq), get(m, r, 2*i + 2, lq, rq));
	}

	int set(int l, int r, int i, int k, int v) {
		if (k < l || r <= k) return a[i];
		if (l + 1 == r) return a[i] = v;
		int m = (l + r)/2;
		return a[i] = max(set(l, m, 2*i + 1, k, v), set(m, r, 2*i + 2, k, v));
	}
};


struct SegTeMa{
	vector<int> a;

	int build(int l, int r, int i, vector<int>& in) {
		if (l + 1 == r) return a[i] = in[l];
		int m = (l + r)/2;
		return a[i] = max(build(l, m, 2*i + 1, in), build(m, r, 2*i + 2, in));
	}

	int firLe(int l, int r, int i, int k, int hi) {
		if (l > k) return -1;
		if (a[i] < hi) return -1;
		if (l + 1 == r) return l;
		int m = (l + r)/2;
		int reR = firLe(m, r, 2*i + 2, k, hi);
		if (reR != -1) return reR;
		return firLe(l, m, 2*i + 1, k, hi);
	}

	int firRi(int l, int r, int i, int k, int hi) {
		if (r <= k) return -1;
		if (a[i] < hi) return -1;
		if (l + 1 == r) return l;
		int m = (l + r)/2;
		int reR = firRi(l, m, 2*i + 1, k, hi);
		if (reR != -1) return reR;
		return firRi(m, r, 2*i + 2, k, hi);
	}
};

struct Node {
	int l, r, leR, riR, su, mi, ma;
};

tuple<int,int,int> comb(tuple<int,int,int> l, tuple<int,int,int> r) {
	return {get<0>(l) + get<0>(r), min(get<1>(l), get<1>(r)), max(get<2>(l), get<2>(r))};
}

struct SegTePer{
	vector<Node> a;

	void build(int i, int l, int r) {
		a[i].leR = l; a[i].riR = r; a[i].su = 0;
		a[i].mi = 1e9; a[i].ma = -1;
		if (l + 1 == r) return;
		int m = (l + r)/2;
		a[i].l = a.size();
		a.push_back({});
		build(a[i].l, l, m);
		a[i].r = a.size();
		a.push_back({});
		build(a[i].r, m, r);
	}

	int inc(int i, int k) {
		if (a[i].leR > k || a[i].riR <= k) return i;
		if (a[i].leR + 1 == a[i].riR) {
			a.push_back(a[i]);
			a.back().su++;
			a.back().mi = a.back().ma = a[i].leR;
			return a.size() - 1;
		}
		int le = inc(a[i].l, k), ri = inc(a[i].r, k);
		a.push_back({le, ri, a[i].leR, a[i].riR, a[le].su + a[ri].su, min(a[le].mi, a[ri].mi), max(a[le].ma, a[ri].ma)});
		return a.size() - 1;
	}

	tuple<int,int,int> get(int i, int lq, int rq) {
		if (a[i].riR <= lq || rq <= a[i].leR) return {0, 1e9, -1};
		if (lq <= a[i].leR && a[i].riR <= rq) return {a[i].su, a[i].mi, a[i].ma};
		return comb(get(a[i].l, lq, rq), get(a[i].r, lq, rq));
	}
};


struct DifStr{
	int mi, ma, leD, riD;
};

DifStr comb(DifStr l, DifStr r) {
	return {min(l.mi, r.mi), max(l.ma, r.ma), max(l.leD, max(r.leD, r.ma - l.mi)), max(l.riD, max(r.riD, l.ma - r.mi))};
}

struct SegTeDif {
	vector<DifStr> a;

	DifStr build(int l, int r, int i, vector<int> &in) {
		if (l + 1 == r) return a[i] = {in[l], in[l], 0, 0};
		int m = (l + r) / 2;
		return a[i] = comb(build(l, m, 2 * i + 1, in), build(m, r, 2 * i + 2, in));
	}

	DifStr get(int l, int r, int i, int lq, int rq) {
		if (rq <= l || r <= lq) return {(int)1e9, -1, 0, 0};
		if (lq <= l && r <= rq) return a[i];
		int m = (l + r)/2;
		return comb(get(l, m, 2*i + 1, lq, rq), get(m, r, 2*i + 2, lq,rq));
	}
};

SegTePer perSe;
vector<pair<int,int>> whi;
SegTeMa maSe;
SegTeDif diSe;
int n;
vector<int> h;

void init(int N, std::vector<int> H) {
	n = N;
	h = H;
	maSe = SegTeMa{vector<int>(4*N)};
	SegTeRan raSe{vector<int>(4*N, 0)};
	diSe = SegTeDif{vector<DifStr>(4*N)};
	diSe.build(0, N, 0, H);
	maSe.build(0, N, 0, H);
	vector<int> o(N);
	std::iota(o.begin(), o.end(),0);
	std::sort(o.begin(), o.end(), [&](int l, int r){return H[l] < H[r];});
	vector<pair<int,int>> ch;
	for (int i = 0; i < N; ++i) {
		int l = 0, r = 1e9 + 1;
		while (l + 1 < r) {
			int m = l + (r  - l)/2;
			int leB = maSe.firLe(0, N, 0, o[i], H[o[i]] + m), reB = maSe.firRi(0, N, 0, o[i], H[o[i]] + m);
			if (leB == -1) leB = 0;
			if (reB == -1) reB = N;
			if (raSe.get(0, N, 0, leB, reB) < m) l = m;
			else r = m;
		}
		raSe.set(0, N, 0, o[i], l);
		ch.push_back({l, o[i]});
	}
	std::sort(ch.begin(), ch.end(), greater<>());
	perSe.a.push_back({});
	whi.push_back({1e9 + 1, 0});
	perSe.build(0, 0, N);
	for (int i = 0; i < N; ++i) {
		whi.push_back({ch[i].first, perSe.inc(whi.back().second, ch[i].second)});
	}
}


int max_towers(int L, int R, int D) {
	int to = std::lower_bound(whi.rbegin(), whi.rend(),make_pair(D, 0))->second;
	auto [su, mi, ma] = perSe.get(to, L, R + 1);
	if (su == 0) {
		su = 1;
		int l = L + 1, r = R + 2;
		while (l + 1 < r) {
			int m = (l + r)/2;
			if (diSe.get(0, n, 0, L, m).leD >= D) r = m;
			else l = m;
		}
		if (r <= R) {
			su += (diSe.get(0, n, 0, r - 1, R + 1).riD >= D);
		}
	} else {
		int lB = maSe.firLe(0, n, 0, mi, h[mi] + D), rB = maSe.firRi(0, n, 0, ma, h[ma] + D);
		if (lB > L) {
			su += (diSe.get(0, n, 0, L, lB+ 1).leD >= D);
		}
		if (rB < R) {
			su += (diSe.get(0, n, 0, rB, R + 1).riD >= D);
		}
	}
	return su;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 700 ms 67112 KB 28917th lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 6 ms 1564 KB Output is correct
3 Correct 6 ms 1816 KB Output is correct
4 Correct 7 ms 1560 KB Output is correct
5 Correct 7 ms 1564 KB Output is correct
6 Correct 11 ms 1640 KB Output is correct
7 Correct 7 ms 1564 KB Output is correct
8 Correct 6 ms 1564 KB Output is correct
9 Correct 8 ms 1564 KB Output is correct
10 Correct 6 ms 1608 KB Output is correct
11 Correct 12 ms 1564 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 7 ms 1564 KB Output is correct
14 Correct 5 ms 1564 KB Output is correct
15 Correct 7 ms 1564 KB Output is correct
16 Correct 7 ms 1564 KB Output is correct
17 Correct 7 ms 1564 KB Output is correct
18 Correct 5 ms 1564 KB Output is correct
19 Correct 10 ms 1564 KB Output is correct
20 Incorrect 6 ms 1624 KB 1st lines differ - on the 1st token, expected: '670', found: '671'
21 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 6 ms 1564 KB Output is correct
3 Correct 6 ms 1816 KB Output is correct
4 Correct 7 ms 1560 KB Output is correct
5 Correct 7 ms 1564 KB Output is correct
6 Correct 11 ms 1640 KB Output is correct
7 Correct 7 ms 1564 KB Output is correct
8 Correct 6 ms 1564 KB Output is correct
9 Correct 8 ms 1564 KB Output is correct
10 Correct 6 ms 1608 KB Output is correct
11 Correct 12 ms 1564 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 7 ms 1564 KB Output is correct
14 Correct 5 ms 1564 KB Output is correct
15 Correct 7 ms 1564 KB Output is correct
16 Correct 7 ms 1564 KB Output is correct
17 Correct 7 ms 1564 KB Output is correct
18 Correct 5 ms 1564 KB Output is correct
19 Correct 10 ms 1564 KB Output is correct
20 Incorrect 6 ms 1624 KB 1st lines differ - on the 1st token, expected: '670', found: '671'
21 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1071 ms 70704 KB Output is correct
2 Incorrect 1137 ms 72544 KB 6556th lines differ - on the 1st token, expected: '16760', found: '16761'
3 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 311 ms 18484 KB 1st lines differ - on the 1st token, expected: '7197', found: '7198'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 600 KB Output is correct
2 Correct 6 ms 1564 KB Output is correct
3 Correct 6 ms 1816 KB Output is correct
4 Correct 7 ms 1560 KB Output is correct
5 Correct 7 ms 1564 KB Output is correct
6 Correct 11 ms 1640 KB Output is correct
7 Correct 7 ms 1564 KB Output is correct
8 Correct 6 ms 1564 KB Output is correct
9 Correct 8 ms 1564 KB Output is correct
10 Correct 6 ms 1608 KB Output is correct
11 Correct 12 ms 1564 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 7 ms 1564 KB Output is correct
14 Correct 5 ms 1564 KB Output is correct
15 Correct 7 ms 1564 KB Output is correct
16 Correct 7 ms 1564 KB Output is correct
17 Correct 7 ms 1564 KB Output is correct
18 Correct 5 ms 1564 KB Output is correct
19 Correct 10 ms 1564 KB Output is correct
20 Incorrect 6 ms 1624 KB 1st lines differ - on the 1st token, expected: '670', found: '671'
21 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 700 ms 67112 KB 28917th lines differ - on the 1st token, expected: '2', found: '3'
2 Halted 0 ms 0 KB -