#include "towers.h"
#include <vector>
#include <cstdio>
#include <algorithm>
using namespace std;
// <|°_°|>
// M. Broccoli
// The hardest choices require the strongest wills
// What is better - to be born good, or to overcome your evil nature with great effort ?
const int MAX_TOWERS = (1e5);
const int LOG = (17);
const int SIZE = (1 << LOG);
struct node {
int left, right, sum;
};
vector <pair <int, int>> Root;
vector <node> Tree;
int TreeMax[2 * MAX_TOWERS];
int TreeMin[2 * MAX_TOWERS];
pair <int, int> Valleys[MAX_TOWERS];
int nbTowers;
int Copy(int a, int &b) {
Tree.push_back(Tree[a]);
return b = Tree.size() - 1;
}
int MakeRoot(int a = 1) {
Root.push_back({0, Copy(Root.back().second, a)});
return Root.back().second;
}
void Remove(int node, int target, int left = 0, int right = SIZE) {
Tree[node].sum --;
if (right - left == 1)
return;
int mid = (left + right) >> 1;
if (target < mid)
Remove(Copy(Tree[node].left, Tree[node].left), target, left, mid);
else
Remove(Copy(Tree[node].right, Tree[node].right), target, mid, right);
return;
}
int GetSum(int node, int qleft, int qright, int left = 0, int right = SIZE) {
if (left >= qright || right <= qleft)
return 0;
if (qleft <= left && right <= qright)
return Tree[node].sum;
int mid = (left + right) >> 1;
return GetSum(Tree[node].left, qleft, qright, left, mid) + GetSum(Tree[node].right, qleft, qright, mid, right);
}
int GetPrev(int node, int target, int left = 0, int right = SIZE) {
if (!Tree[node].sum)
return -1;
if (right - left == 1)
return left;
int mid = (left + right) >> 1;
int ans = -1;
if (target > mid)
ans = GetPrev(Tree[node].right, target, mid, right);
return ans < 0 ? GetPrev(Tree[node].left, target, left, mid) : ans;
}
int GetNext(int node, int target, int left = 0, int right = SIZE) {
if (!Tree[node].sum)
return -1;
if (right - left == 1)
return left;
int mid = (left + right) >> 1;
int ans = -1;
if (target + 1 < mid)
ans = GetNext(Tree[node].left, target, left, mid);
return ans < 0 ? GetNext(Tree[node].right, target, mid, right) : ans;
}
int GetMax(int left, int right) {
int ans = 0;
for (left += nbTowers, right += nbTowers; left < right; left >>= 1, right >>= 1)
{
if (left & 1)
ans = max(ans, TreeMax[left ++]);
if (right & 1)
ans = max(ans, TreeMax[-- right]);
}
return ans;
}
int Mini(int a, int b) {
return TreeMax[a + nbTowers] < TreeMax[b + nbTowers] ? a : b;
}
int GetMin(int left, int right) {
int ans = left;
for (left += nbTowers, right += nbTowers; left < right; left >>= 1, right >>= 1)
{
if (left & 1)
ans = Mini(ans, TreeMin[left ++]);
if (right & 1)
ans = Mini(ans, TreeMin[-- right]);
}
return ans;
}
void init(int N, vector <int> H) {
nbTowers = N;
Tree.resize(2 * SIZE, {-1, -1, 0});
int cnt = 0;
for (int i = 0; i < nbTowers; i ++)
{
TreeMax[i + nbTowers] = H[i];
TreeMin[i + nbTowers] = i;
if ((!i || H[i] < H[i - 1]) && (i + 1 == nbTowers || H[i] < H[i + 1]))
{
Tree[i + SIZE].sum = 1;
Valleys[cnt ++] = {H[i], i};
}
}
for (int i = SIZE - 1; i; i --)
{
Tree[i] = {2 * i, 2 * i + 1, Tree[2 * i].sum + Tree[2 * i + 1].sum};
}
for (int i = nbTowers - 1; i; i --)
{
TreeMax[i] = max(TreeMax[2 * i], TreeMax[2 * i + 1]);
TreeMin[i] = Mini(TreeMin[2 * i], TreeMin[2 * i + 1]);
}
Root.push_back({0, 1});
sort(Valleys, Valleys + cnt);
for (int i = cnt - 1; i; i --)
{
int id = Valleys[i].second;
int root = MakeRoot();
Remove(root, id);
int left = GetPrev(root, id);
int right = GetNext(root, id);
left = left < 0 ? 1 << 30 : GetMax(left, id);
right = right < 0 ? 1 << 30 : GetMax(id, right);
Root.back().first = min(left, right) - TreeMax[id + nbTowers];
}
return;
}
int max_towers(int left, int right, int delta) {
int root = 0;
int sz = Root.size();
for (int jump = SIZE; jump; jump >>= 1)
{
if (jump + root < sz && delta > Root[jump + root].first)
root += jump;
}
root = Root[root].second;
int ans = GetSum(root, left, ++ right);
if (!ans)
return 1;
int next = GetNext(root, left - 1), prev = GetPrev(root, right);
left = GetMin(left, next), right = GetMin(prev, right);
ans += GetMax(left, next) - delta >= max(TreeMax[left + nbTowers], TreeMax[next + nbTowers]);
ans += GetMax(prev, right) - delta >= max(TreeMax[prev + nbTowers], TreeMax[right - nbTowers]);
return ans;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
429 ms |
7848 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6480 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6480 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
36 ms |
18612 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
306 ms |
6992 KB |
1st lines differ - on the 1st token, expected: '7197', found: '5956' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
6480 KB |
1st lines differ - on the 1st token, expected: '13', found: '15' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
429 ms |
7848 KB |
12th lines differ - on the 1st token, expected: '2', found: '1' |
| 2 |
Halted |
0 ms |
0 KB |
- |
