| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 626299 |
2022-08-11T11:11:40 Z |
ITO |
Radio Towers (IOI22_towers) |
C++17 |
|
4000 ms |
19076 KB |
#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
int n, h[100005], hi[100005], mama[100005];
vector<pair<int, int>> pv;
int av[400000], bv[400000];
vector<int> aa[400000];
int build(int id, int ll, int rr) {
if (ll == rr) {
av[id] = h[ll];
bv[id] = mama[ll];
if (bv[id] == 2000000001) bv[id] = -1000000001;
aa[id].push_back(mama[ll]);
} else {
int m = (ll + rr) / 2, i = 0, j = 0;
av[id] = min(build(id * 2, ll, m), build(id * 2 + 1, m + 1, rr));
bv[id] = max(bv[id * 2], bv[id * 2 + 1]);
while (i < aa[id * 2].size() && j < aa[id * 2 + 1].size()) {
if (aa[id * 2][i] <= aa[id * 2 + 1][j]) {
aa[id].push_back(aa[id * 2][i]);
i++;
} else {
aa[id].push_back(aa[id * 2 + 1][j]);
j++;
}
}
while (i < aa[id * 2].size()) {
aa[id].push_back(aa[id * 2][i]);
i++;
}
while (j < aa[id * 2 + 1].size()) {
aa[id].push_back(aa[id * 2 + 1][j]);
j++;
}
}
return av[id];
}
int mi(int id, int l, int r, int ll, int rr) {
if (r < ll || l > rr) return 2000000001;
if (ll >= l && rr <= r) return av[id];
int m = (ll + rr) / 2;
return min(mi(id * 2, l, r, ll, m), mi(id * 2 + 1, l, r, m + 1, rr));
}
int lar(int id, int va, int l, int r, int ll, int rr) {
if (r < ll || l > rr || bv[id] < va) return -1;
if (ll == rr) return ll;
int m = (ll + rr) / 2;
int te = lar(id * 2 + 1, va, l, r, m + 1, rr);
if (te >= 0) return te;
return lar(id * 2, va, l, r, ll, m);
}
int lal(int id, int va, int l, int r, int ll, int rr) {
if (r < ll || l > rr || bv[id] < va) return -1;
if (ll == rr) return ll;
int m = (ll + rr) / 2;
int te = lal(id * 2, va, l, r, ll, m);
if (te >= 0) return te;
return lal(id * 2 + 1, va, l, r, m + 1, rr);
}
int bel(int id, int va, int l, int r, int ll, int rr) {
if (r < ll || l > rr) return 0;
if (ll >= l && r >= rr) {
return upper_bound(aa[id].begin(), aa[id].end(), va) - aa[id].begin();
}
int m = (ll + rr) / 2;
return bel(id * 2, va, l, r, ll, m) + bel(id * 2 + 1, va, l, r, m + 1, rr);
}
int rii[100005], lee[100005];
void init(int N, std::vector<int> H) {
n = N;
pv.push_back({-2000000001, -1});
for (int i = 0; i < N; i++) {
mama[i] = 2000000001;
h[i] = H[i];
int te = pv.size();
if (te >= 2 && ((pv[te - 1].first > pv[te - 2].first && h[i] > pv[te - 1].first) || (pv[te - 1].first < pv[te - 2].first && h[i] < pv[te - 1].first))) {
pv[te - 1] = make_pair(h[i], i);
} else {
pv.push_back({h[i], i});
}
hi[i] = (pv.size() - 1);
}
int te = pv.size();
if ((pv[te - 1].first > pv[te - 2].first && -1000000001 > pv[te - 1].first) || (pv[te - 1].first < pv[te - 2].first && -1000000001 < pv[te - 1].first)) {
pv[te - 1] = make_pair(-1000000001, N);
} else {
pv.push_back({-1000000001, N});
}
te = pv.size();
priority_queue<pair<int, int>> pq;
for (int i = 1; i < te; i++) {
pq.push({-abs(pv[i].first - pv[i - 1].first), i - 1});
rii[i - 1] = i;
lee[i] = i - 1;
}
int xx = te / 2;
while (1) {
pair<int, int> pin = pq.top();
pq.pop();
if (lee[pin.second] == -1 || lee[rii[pin.second] == -1]) continue;
pq.push({-abs(pv[lee[pin.second]].first - pv[rii[rii[pin.second]]].first), lee[pin.second]});
if (pv[pin.second].first > pv[rii[pin.second]].first) {
mama[pv[pin.second].second] = -pin.first;
} else {
mama[pv[rii[pin.second]].second] = -pin.first;
}
xx--;
if (!xx) break;
rii[lee[pin.second]] = rii[rii[pin.second]];
lee[rii[rii[pin.second]]] = lee[pin.second];
lee[pin.second] = -1;
lee[rii[pin.second]] = -1;
}
build(1, 0, N - 1);
}
int max_towers(int L, int R, int D) {
int lai = lal(1, D, L, R, 0, n - 1), rai = lar(1, D, L, R, 0, n - 1);
if (L == R || lai == -1) return 1;
int co = (hi[rai] - hi[lai]) / 2 - bel(1, D - 1, lai, rai, 0, n - 1);
if (h[lai] - mi(1, L, lai, 0, n - 1) >= D) co++;
if (h[rai] - mi(1, rai, R, 0, n - 1) >= D) co++;
return co;
}
Compilation message
towers.cpp: In function 'int build(int, int, int)':
towers.cpp:21:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | while (i < aa[id * 2].size() && j < aa[id * 2 + 1].size()) {
| ~~^~~~~~~~~~~~~~~~~~~
towers.cpp:21:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | while (i < aa[id * 2].size() && j < aa[id * 2 + 1].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:30:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
30 | while (i < aa[id * 2].size()) {
| ~~^~~~~~~~~~~~~~~~~~~
towers.cpp:34:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | while (j < aa[id * 2 + 1].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
19076 KB |
18th lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4067 ms |
9680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4067 ms |
9680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4069 ms |
14176 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4067 ms |
10576 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4067 ms |
9680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
499 ms |
19076 KB |
18th lines differ - on the 1st token, expected: '1', found: '0' |
| 2 |
Halted |
0 ms |
0 KB |
- |
