#include "bits/stdc++.h"
using namespace std;
using ll = long long;
#define sz(v) ((int)(v).size())
#define pb push_back
int n;
vector<int> h;
const int inf = 1e9+7;
struct aint {
int n, neut;
vector<int> f;
int (*fn)(const int, const int);
aint(int _n, int _neut, int (*_fn)(const int, const int)) {
n = _n; neut = _neut;
fn = _fn;
f.assign(n<<1, neut);
}
int
query(int l, int r)
{
int res = neut;
for (l += n, r+=n+1; l < r; l>>=1, r>>=1) {
if (l&1) res = fn(res, f[l++]);
if (r&1) res = fn(res, f[--r]);
}
return res;
}
void
upd(int x, int v) {
x+=n;
for (f[x] = v; x > 1; x>>=1) {
f[x>>1] = fn(f[x], f[x^1]);
}
}
};
struct paint {
int n, neut;
int (*fn)(const int, const int);
vector<array<int, 3>> f; /* val, l, r */
int cn = 0;
paint(int _n, int _neut, int (*_fn)(const int, const int))
{
fn = _fn;
n = _n; neut = _neut;
f.assign(max(20*n, (int)2e5), {neut, -1, -1});
}
void chkalloc() {if (cn == sz(f)) f.resize(sz(f)+max(n, 100)); }
int newv(int val) {
chkalloc();
f[cn] = {val, -1, -1};
return cn++;
}
int newv(int l, int r) {
chkalloc();
f[cn] = {fn(f[l][0], f[r][0]), l, r};
return cn++;
}
int build(int l, int r) {
if (l == r)
return newv(neut);
int tm = (l+r)>>1;
return newv(build(l, tm), build(tm+1, r));
}
int query(int i, int l, int r) { return query(i, 0, n-1, l, r); }
int query(int i, int l, int r, int tl, int tr) {
if (l >= tl && r <= tr) return f[i][0];
if (r < tl || l >= tr) return neut;
assert(i >= 0);
int m = (r + l) >> 1;
return fn(query(f[i][1], l, m, tl, tr), query(f[i][2], m+1, r, tl, tr));
}
int upd(int i, int x, int v) { return upd(i, 0, n-1, x, v); }
int upd(int i, int l, int r, int x, int v) {
if (l == r) return newv(v);
int m = (l + r)>>1;
if (x <= m)
return newv(upd(f[i][1], l, m, x, v), f[i][2]);
else
return newv(f[i][1], upd(f[i][2], m+1, r, x, v));
}
};
aint *tmnh, *tmxh;
paint *p1, *p2, *p3; /* p1 = sum; p2 = left pos; p3 = right pos */
map<int, int> hpos, dind;
vector<array<int, 3>> edg;
set<int> deltas;
const int N = 1e5;
int ip1[N+5], ip2[N+5], ip3[N+5];
int ev[N+5];
int mn(int a, int b) { return min(a, b); }
int mx(int a, int b) { return max(a, b); }
int sm(int a, int b) { return a + b; }
int
max_towers(int l, int r, int d)
{
if (l == r) return 1;
if (l + 1 == r) return 1;
auto it = deltas.lower_bound(d);
if (it == deltas.end()) return 1;
int x = dind[*it];
int ans = 0;
int v, z, u = p2->query(ip2[x], l, r);
if (u <= r && u > l) {
z = hpos[tmnh->query(l, u-1)];
v = hpos[tmxh->query(l, u-1)];
l = u+1;
if (h[u] - h[z])
++ans;
}
if (l > r) return ans;
u = p3->query(ip3[x], l, r);
if (u < r && u >= l) {
z = hpos[tmnh->query(u+1, r)];
v = hpos[tmxh->query(u+1, r)];
r = u-1;
if (h[u] - h[z])
++ans;
}
if (l > r) return ans;
ans += p1->query(ip1[x], l, r);
return max(ans, 1);
}
void
dfs(int x, int l, int r) {
int y, z;
if (l == r) return;
if (x > l) {
y = tmnh->query(l, x-1);
z = hpos[tmxh->query(l, x-1)];
edg.pb({h[x] - y, x, z});
dfs(z, l, x-1);
}
if (x < r) {
y = tmnh->query(x+1, r);
z = hpos[tmxh->query(x+1, r)];
edg.pb({h[x] - y, x, z});
dfs(z, x+1, r);
}
}
void
init(int _n, std::vector<int> _h)
{
n = _n;
h = _h;
tmnh = new aint(n, inf+10, mn);
tmxh = new aint(n, -1, mx);
for (int i = 0; i < n; ++i) {
tmnh->upd(i, h[i]);
tmxh->upd(i, h[i]);
hpos[h[i]] = i;
}
dfs(hpos[tmxh->query(0, n-1)], 0, n-1);
sort(edg.begin(), edg.end());
reverse(edg.begin(), edg.end());
for (auto x : edg) {
deltas.insert(x[0]);
ev[x[2]] = x[0];
dind[x[0]] = sz(deltas);
}
p1 = new paint(n, 0, sm);
p2 = new paint(n, inf, mn);
p3 = new paint(n, -1, mx);
int lp1, lp2, lp3;
lp1 = p1->build(0, n-1);
lp2 = p2->build(0, n-1);
lp3 = p3->build(0, n-1);
for (auto x : edg) {
lp1 = p1->upd(lp1, x[1], 0);
lp1 = p1->upd(lp1, x[2], 1);
if (x[1] < x[2]) {
lp2 = p2->upd(lp2, x[1], x[1]);
} else {
lp3 = p3->upd(lp3, x[1], x[1]);
}
ip1[dind[x[0]]] = lp1;
ip2[dind[x[0]]] = lp2;
ip3[dind[x[0]]] = lp3;
}
}
Compilation message
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:131:6: warning: variable 'v' set but not used [-Wunused-but-set-variable]
131 | int v, z, u = p2->query(ip2[x], l, r);
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
650 ms |
74432 KB |
2nd lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7760 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7760 KB |
1st lines differ - on the 1st token, expected: '91', found: '93' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7760 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7760 KB |
1st lines differ - on the 1st token, expected: '91', found: '93' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1123 ms |
113536 KB |
4th lines differ - on the 1st token, expected: '13956', found: '13957' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
313 ms |
27540 KB |
1st lines differ - on the 1st token, expected: '7197', found: '7196' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
7376 KB |
Output is correct |
| 2 |
Correct |
6 ms |
7760 KB |
Output is correct |
| 3 |
Incorrect |
5 ms |
7760 KB |
1st lines differ - on the 1st token, expected: '91', found: '93' |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
650 ms |
74432 KB |
2nd lines differ - on the 1st token, expected: '1', found: '2' |
| 2 |
Halted |
0 ms |
0 KB |
- |
