#include "towers.h"
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep2(i, a, b) for (int i = (int)(a); i < (int)(b); ++i)
#define rrep(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define rrep2(i, a, b) for (int i = (int)(b) - 1; i >= (int)(a); --i)
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
using namespace std;
using ll = long long;
template<class T, class U> bool chmin(T& a, const U& b) { return a > b ? a = b, true : false; }
template<class T, class U> bool chmax(T& a, const U& b) { return a < b ? a = b, true : false; }
constexpr ll inf = 1e18;
template<class M>
class SegmentTree {
using T = typename M::T;
int n;
vector<T> dat;
public:
SegmentTree() = default;
SegmentTree(int n_, T x) {
n = 1;
while (n < n_) n *= 2;
dat.assign(2 * n, x);
}
SegmentTree(vector<T> a) {
n = 1;
while (n < a.size()) n *= 2;
dat.assign(2 * n, M::id());
rep (i, a.size()) dat[i + n] = a[i];
rrep2 (i, 1, n) dat[i] = M::op(dat[2 * i], dat[2 * i + 1]);
}
void set(int k, T x) {
k += n;
dat[k] = x;
while (k > 1) {
k /= 2;
dat[k] = M::op(dat[2 * k], dat[2 * k + 1]);
}
}
void apply(int k, T x) { set(k, M::op(dat[k + n], x)); }
T prod(int l, int r) const {
l += n; r += n;
T lsm = M::id(), rsm = M::id();
while (l < r) {
if (l & 1) lsm = M::op(lsm, dat[l++]);
if (r & 1) rsm = M::op(dat[--r], rsm);
l >>= 1; r >>= 1;
}
return M::op(lsm, rsm);
}
T all_prod() const { return dat[1]; }
T get(int k) const { return dat[k + n]; }
};
struct Max {
using T = ll;
static T op(T a, T b) { return max(a, b); }
static T id() { return -inf; }
};
struct Min {
using T = ll;
static T op(T a, T b) { return min(a, b); }
static T id() { return inf; }
};
struct Sum {
using T = ll;
static T op(T a, T b) { return a + b; }
static T id() { return 0; }
};
struct Monoid {
using T = tuple<ll, ll, ll>;
static T op(T a, T b) {
auto [a1, a2, a3] = a;
auto [b1, b2, b3] = b;
return {a1 + b1, min(a2, b2), max(a3, b3)};
}
static T id() { return {0, inf, -inf}; }
};
int N;
vector<int> H, Hs;
SegmentTree<Monoid> seg1, seg2;
SegmentTree<Min> rmq;
vector<ll> ans;
vector<ll> stamps;
int solve(int L, int R, int D) {
++R;
auto [s, l, r] = seg2.prod(L, R);
if (s == 0) return 1;
int res = s - 1;
if (l != L && Hs[rmq.prod(L, l)] + D <= Hs[H[l]]) ++res;
if (r != R - 1 && Hs[rmq.prod(r + 1, R)] + D <= Hs[H[r]]) ++res;
return max(res, 1);
}
void init(int N_, std::vector<int> H_) {
N = N_; H = H_;
Hs = H;
sort(all(Hs));
Hs.erase(unique(all(Hs)), Hs.end());
rep (i, N) H[i] = lower_bound(all(Hs), H[i]) - Hs.begin();
rmq = SegmentTree<Min>(N, inf);
rep (i, N) rmq.set(i, H[i]);
seg1 = seg2 = SegmentTree<Monoid>(N, {0, inf, -inf});
rep (i, N) {
if ((i == 0 || H[i - 1] > H[i]) && (i == N - 1 || H[i] < H[i + 1])) seg1.set(i, {1, i, i});
}
rep (i, N) {
if ((i == 0 || H[i - 1] < H[i]) && (i == N - 1 || H[i] > H[i + 1])) seg2.set(i, {1, i, i});
}
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> que;
rep (i, N) {
if (get<0>(seg2.get(i)) == 1) {
auto [s1, l1, r1] = seg1.prod(0, i);
auto [s2, l2, r2] = seg1.prod(i + 1, N);
ll t = -inf;
if (s1 != 0) chmax(t, Hs[H[r1]]);
if (s2 != 0) chmax(t, Hs[H[l2]]);
que.emplace(Hs[H[i]] - t, i);
}
}
while (!que.empty()) {
auto [d, k] = que.top(); que.pop();
// if (d >= D) break;
ans.push_back(solve(0, N - 1, d));
stamps.push_back(d);
if (get<0>(seg2.get(k)) == 0) continue;
auto [s1, l1, r1] = seg1.prod(0, k);
auto [s2, l2, r2] = seg1.prod(k + 1, N);
{
ll t = -inf;
if (s1 != 0) chmax(t, Hs[H[r1]]);
if (s2 != 0) chmax(t, Hs[H[l2]]);
if (d != Hs[H[k]] - t) continue;
}
if (s1 == 0 && s2 == 0) continue;
if (s1 == 0 || (s2 != 0 && H[r1] < H[l2])) {
seg1.set(l2, {0, inf, -inf});
seg2.set(k, {0, inf, -inf});
auto [s, l, r] = seg2.prod(k + 1, N);
if (s == 0) continue;
auto [s3, l3, r3] = seg1.prod(l + 1, N);
ll t = -inf;
if (s1 != 0) chmax(t, Hs[H[r1]]);
if (s3 != 0) chmax(t, Hs[H[l3]]);
que.emplace(Hs[H[l]] - t, l);
}
else {
seg1.set(r1, {0, inf, -inf});
seg2.set(k, {0, inf, -inf});
auto [s, l, r] = seg2.prod(0, k);
if (s == 0) continue;
auto [s3, l3, r3] = seg1.prod(0, r);
ll t = -inf;
if (s2 != 0) chmax(t, Hs[H[l2]]);
if (s3 != 0) chmax(t, Hs[H[r3]]);
que.emplace(Hs[H[r]] - t, r);
}
}
ans.push_back(solve(0, N - 1, inf));
stamps.push_back(inf);
}
int max_towers(int L, int R, int D) {
auto itr = lower_bound(all(stamps), D) - stamps.begin();
return ans[itr];
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:177:35: warning: overflow in conversion from 'll' {aka 'long long int'} to 'int' changes value from '1000000000000000000' to '-1486618624' [-Woverflow]
177 | ans.push_back(solve(0, N - 1, inf));
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
8536 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
478 ms |
19140 KB |
1st lines differ - on the 1st token, expected: '11903', found: '33010' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
165 ms |
4696 KB |
Output is correct |
| 2 |
Incorrect |
515 ms |
19140 KB |
18744th lines differ - on the 1st token, expected: '1966', found: '1965' |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
1st lines differ - on the 1st token, expected: '13', found: '131' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
242 ms |
8536 KB |
1st lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
