This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <vector>
#include <map>
#include <set>
#include <iostream>
#include <cassert>
#define map std::map
#define set std::set
#define vector std::vector
#define vi vector<int>
#define ll long long
#define pb push_back
#define vll vector<ll>
ll fd = -10;
ll n;
vi heights;
vector<vll> steppers;
void init(int N, vector<int> H){
n = N;
heights = H;
}
void compute(ll d){
vi nhi(n + 1, n);
ll best = -1;
ll vb = -1;
ll last = n;
for (ll i = n - 1; i >= 0; i--){
ll v = heights[i];
if (v > vb){
best = i;
vb = v;
}
if (vb >= v + d){
last = best;
best = -1;
vb = -1;
//std::cout << "UPD HI " << i << " " << last << std::endl;
for (ll j = i + 1; j < last; j++){
if (heights[j] >= heights[i] + d){
last = j;
break;
}
}
best = i;
vb = v;
//std::cout << "UPD HI " << i << " " << last << std::endl;
}
nhi[i] = last;
/*for (int j = i + 1; j < last; j++){
if (heights[j] >= heights[i] + d){
std::cout << "HI " << i << " " << j << " " << last << '\n';
}
}*/
//std::cout << "nhi " << i << " " << last << std::endl;
}
vi nlo(n + 1, n);
ll lbest = -1;
ll lvb = -2e9;
ll llast = n;
for (ll i = n - 1; i >= 0; i--){
ll v = 0 - heights[i];
if (v > lvb){
lbest = i;
lvb = v;
}
if (lvb >= v + d){
llast = lbest;
lbest = -1;
lvb = -2e9;
for (ll j = i + 1; j < llast; j++){
if (heights[i] >= heights[j] + d){
llast = j;
break;
}
}
best = i;
vb = v;
}
/*for (int j = i + 1; j < last; j++){
if (heights[i] >= heights[j] + d){
std::cout << "LO" << " " << i << " " << j << " " << llast << '\n';
}
}*/
nlo[i] = llast;
}
steppers = vector<vll>();
vll first;
for (ll i = 0; i <= n; i++){
first.pb(nlo[nhi[i]]);
}
steppers.pb(first);
for (ll j = 0; j < 30; j++){
vll nex;
vll curr = steppers[j];
for (ll i = 0; i <= n; i++){
nex.pb(curr[curr[i]]);
}
steppers.pb(nex);
}
//std::cout << steppers.size() << std::endl;
}
int max_towers(int L, int R, int D){
if (D != fd){
compute(D);
fd = D;
}
ll out = 1;
ll curr = L;
for (ll j = 29; j >= 0; j--){
//std::cout << j << " " << out << " " << curr << std::endl;
ll att = steppers[j][curr];
if (att <= R){
out += (1 << j);
curr = att;
}
}
return out;
}
/*
7 3
10 21 60 40 50 30 70
1 5 10
2 2 100
0 6 17
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |