#include "towers.h"
#include <algorithm>
#include <iostream>
#include <vector>
typedef long long ll;
using namespace std;
const int maxn = 1 << 17, inf = 2e9 + 5;
struct node1 { int mi, mx, dix, dxi; node1() { mi = inf, mx = -inf, dix = 0, dxi = 0; } };
vector<node1> tmx(maxn * 2);
vector<int> h;
node1 merge(node1 l, node1 r)
{
node1 n;
n.mi = min(l.mi, r.mi);
n.mx = max(l.mx, r.mx);
n.dix = max({ l.dix, r.dix, r.mx - l.mi });
n.dxi = max({ l.dxi, r.dxi, l.mx - r.mi });
return n;
}
node1 query(int l, int r)
{
node1 n1, n2;
for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) n1 = merge(n1, tmx[l++]);
if (r & 1) n2 = merge(tmx[--r], n2);
}
return merge(n1, n2);
}
struct node2 { int tim, mi, mx; };
bool cmp(node2 a, node2 b) { return a.tim < b.tim; }
bool cmp2(node2 a, int t) { return a.tim < t; }
vector<vector<node2> > tr(maxn * 2);
void update(int i, int t, int x)
{
for (i += maxn; i > 0; i >>= 1) tr[i].push_back({ t, x, x });
}
void upd(int vr, int t, int& mi, int& mx, int& cnt)
{
int i = lower_bound(tr[vr].begin(), tr[vr].end(), t, cmp2) - tr[vr].begin();
if (i == tr[vr].size()) return;
mi = min(mi, tr[vr][i].mi), mx = max(mx, tr[vr][i].mx), cnt += tr[vr].size() - i;
}
void query(int l, int r, int t, int& mi, int& mx, int& cnt)
{
for (l += maxn, r += maxn + 1; l < r; l >>= 1, r >>= 1)
{
if (l & 1) upd(l++, t, mi, mx, cnt);
if (r & 1) upd(--r, t, mi, mx, cnt);
}
}
void init(int n, vector<int> H)
{
h = H;
for (int i = 0; i < n; i++) tmx[maxn + i].mi = tmx[maxn + i].mx = h[i];
for (int i = maxn - 1; i > 0; i--) tmx[i] = merge(tmx[(i << 1)], tmx[(i << 1) | 1]);
vector<int> l(n, -1), r(n, n);
vector<int> st;
for (int i = 0; i < n; i++)
{
while (!st.empty() && h[st.back()] > h[i]) st.pop_back();
if (!st.empty()) l[i] = st.back();
st.push_back(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--)
{
while (!st.empty() && h[st.back()] > h[i]) st.pop_back();
if (!st.empty()) r[i] = st.back();
st.push_back(i);
}
for (int i = 0; i < n; i++)
{
int ml = (l[i] == -1 ? inf : query(l[i] + 1, i - 1).mx), mr = (r[i] == n - 1 ? inf : query(i + 1, r[i] - 1).mx);
int t = max(0, min(ml - h[i], mr - h[i]));
update(i, t, i);
}
for (int i = 0; i < maxn * 2; i++)
{
sort(tr[i].begin(), tr[i].end(), cmp);
for (int j = (int)tr[i].size() - 2; j >= 0; j--) tr[i][j].mi = min(tr[i][j].mi, tr[i][j + 1].mi), tr[i][j].mx = max(tr[i][j].mx, tr[i][j + 1].mx);
}
}
int max_towers(int l, int r, int d)
{
int lo = l, hi = r + 1;
while (lo < hi) // chceme najst prvy index...
{
int m = (lo + hi) / 2;
if (query(l, m).dix >= d) hi = m; // mozeme ist nizsie
else lo = m + 1;
}
int li = lo;
lo = l - 1, hi = r;
while (lo < hi) // chceme najst posledny index...
{
int m = (lo + hi + 1) / 2;
if (query(m, r).dxi >= d) lo = m; // mozeme ist vyssie
else hi = m - 1;
}
int ri = lo;
int mi = inf, mx = -inf, cnt = 0;
query(l, r, d, mi, mx, cnt);
if (cnt == 0) return 1 + (int)(li <= ri);
if (query(li, mi).mx >= h[mi] + d) cnt++;
if (query(mx, ri).mx >= h[mx] + d) cnt++;
return cnt;
}
Compilation message
towers.cpp: In function 'void upd(int, int, int&, int&, int&)':
towers.cpp:42:8: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node2>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | if (i == tr[vr].size()) return;
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
627 ms |
26356 KB |
1st lines differ - on the 1st token, expected: '1', found: '21740' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10576 KB |
1st lines differ - on the 1st token, expected: '13', found: '45' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10576 KB |
1st lines differ - on the 1st token, expected: '13', found: '45' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1278 ms |
36816 KB |
1st lines differ - on the 1st token, expected: '11903', found: '35202' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
370 ms |
16852 KB |
1st lines differ - on the 1st token, expected: '7197', found: '22570' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
10576 KB |
1st lines differ - on the 1st token, expected: '13', found: '45' |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
627 ms |
26356 KB |
1st lines differ - on the 1st token, expected: '1', found: '21740' |
| 2 |
Halted |
0 ms |
0 KB |
- |
