#include "towers.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
using pl = pair<ll, ll>;
using vl = vector<ll>;
#define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
#define FD(i, l, r) for (ll i = ll(l); i > ll(r); --i)
#define A(a) (a).begin(), (a).end()
#define K first
#define V second
template<typename T> struct SparseTable {
int n,log2=0;
function<T(T, T)> merge;
T id ;
vector<vector<T>> a = {{}};
SparseTable(const vector<T>& v, function<T(T, T)> _merge, T _id): merge(_merge), id(_id) {
n = v.size();
while((1<<log2) <= n) {
++log2;
}
a.resize(log2);
a[0] = v;
for(int i=1,len=1;i<log2;++i,len*=2) {
a[i].resize(n + 1 - (1<<i));
for(size_t j=0;j<a[i].size();++j) {
a[i][j] = merge(a[i-1][j], a[i-1][j + len]);
}
}
}
SparseTable(){}
T query(int l, int r) { // [l,r)
if (r <= l) return id;
int len = __lg(r-l);
return merge(a[len][l], a[len][r- (1<<len)]);
}
};
SparseTable<ll> spmin;
const int MAXN = 100010, INF = 1000000010;
namespace seg {
pl merge(pl a, pl b) {
return pair(min(a.K, b.K), max(a.V, b.V));
}
struct node{
vector<pl> vec;
vector<pl> indices; // {mn, mx}
node(){};
node(int value, int pos){
vec.emplace_back(value, pos);
indices.emplace_back(pos, pos);
}
node(node& a, node& b){
vec.resize(a.vec.size() + b.vec.size());
indices.resize(vec.size());
merge(a.vec.begin(), a.vec.end(), b.vec.begin(), b.vec.end(), vec.begin());
pl cur(MAXN, -1);
// All items are now in sorted order, relative to first key.
// Now mn and max represent the range of indices or something?
// for the suffix max.
FD(i, ll(vec.size())-1, -1) indices[i] = merge(pair(vec[i].V, vec[i].V), cur);
}
};
node tr[2*MAXN];
pair<int, pl> query(int l, int r, int x){
int ret=0;
pl res(MAXN, -1);
auto handle = [&](node& cur) {
auto &[vec, indices] = cur;
auto itr = lower_bound(A(vec), pair(x, -1));
int pos = (int)(itr - vec.begin());
ret += (int)(vec.end() - itr);
if(itr!=vec.end()) res = merge(res, indices[pos]);
};
for(l+=MAXN, r+=MAXN; l<r; l>>=1, r>>=1){
if(l&1) handle(tr[l++]);
if(r&1) handle(tr[--r]);
}
return {ret, res};
}
void build(vl res) {
F(i, 0, res.size()) seg::tr[MAXN+i]=seg::node(res[i], i);
FD(i, MAXN-1, -1) tr[i]=node(tr[i<<1], tr[i<<1|1]);
}
}
int arr[MAXN];
void init(int n, vector<int> H) {
vl maxl(n), maxr(n);
copy(A(H), arr);
spmin = SparseTable<ll>(H, [](ll a, ll b) {
return min(a, b);
}, INF);
F(i, 0, n) {
int x;
for(x=i-1; x!=-1 && H[x]<H[i]; x=maxl[x]);
maxl[i]=x;
}
FD(i, n-1, -1) {
int x;
for(x=i+1; x!=n && H[x]<H[i]; x=maxr[x]);
maxr[i]=x;
}
// maxl and maxr finds closest node greater than it to left and right
vl res(n);
F(i, 0, n) cout << H[i] << " "; cout << endl;
F(i, 0, n) {
int l = maxl[i], r = maxr[i];
int a = H[i] - spmin.query(l+1, i);
int b = H[i] - spmin.query(i+1, r);
res[i] = min(a, b);
}
// Somehow, res is now filled with like
// "Consider only the peaks of the array. Now, when we scan left/right until we hit another peak",
// find the min item in both sides.
// Do above equation
F(i, 0, n) cout << res[i] << " "; cout << endl;
seg::build(res);
}
int max_towers(int L, int R, int D) {
auto [ret, indices] = seg::query(L, R+1, D);
if(!ret == 0) return 1;
auto [mn, mx] = indices;
int sa = (spmin.query(L, mn) > arr[mn] - D);
int sb = (spmin.query(mx+1, R+1) > arr[mx] - D);
return max(0, ret - sa - sb) + 1;
}
Compilation message
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:8:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
8 | #define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
| ^~~
towers.cpp:125:5: note: in expansion of macro 'F'
125 | F(i, 0, n) cout << H[i] << " "; cout << endl;
| ^
towers.cpp:125:37: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
125 | F(i, 0, n) cout << H[i] << " "; cout << endl;
| ^~~~
towers.cpp:8:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
8 | #define F(i, l, r) for (ll i = ll(l); i < ll(r); ++i)
| ^~~
towers.cpp:137:5: note: in expansion of macro 'F'
137 | F(i, 0, n) cout << res[i] << " "; cout << endl;
| ^
towers.cpp:137:39: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
137 | F(i, 0, n) cout << res[i] << " "; cout << endl;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
14 ms |
14936 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
10072 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
10072 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
24 ms |
18328 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
8 ms |
11952 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
4 ms |
10072 KB |
Possible tampering with the output or unexpected termination of the program |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
14 ms |
14936 KB |
Execution killed with signal 13 |
| 2 |
Halted |
0 ms |
0 KB |
- |
