#include <bits/stdc++.h>
using namespace std;
#include "towers.h"
typedef int ll;
int const M = 1e6 + 10 , lg = 20 , Mx = M * 31;
int n , s[M] , Size = (1 << 30) , sparse[M][lg + 2] , Left[M] , Right[M];
struct sgtree {
int Left[Mx] , Right[Mx] , cur = 1;
vector<ll>elem[Mx];
inline void Init() {
for(int i = 0 ; i < Mx ; ++i) Left[i] = Right[i] = 0;
}
inline void Update(int i , int val , int node = 1 , int lx = 1 , int rx = Size) {
if(lx == rx) {
elem[node].push_back(val);
return;
}
int mid = (lx + rx) / 2;
if(i <= mid) {
if(Left[node] == 0) Left[node] = ++cur;
Update(i , val , Left[node] , lx , mid);
} else {
if(Right[node] == 0) Right[node] = ++cur;
Update(i , val , Right[node] , mid + 1 , rx);
}
}
inline void Build(int node = 1 , int lx = 1 , int rx = Size) {
if(node == 0 || lx == rx) return;
int mid = (lx + rx) / 2;
Build(Left[node] , lx , mid);
Build(Right[node] , mid + 1 , rx);
int l = 0 , r = 0;
while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
if(l == elem[Left[node]].size()) {
elem[node].push_back(elem[Right[node]][r]);
++r;
}
else if(r == elem[Right[node]].size()) {
elem[node].push_back(elem[Left[node]][l]);
++l;
}
else if(elem[Left[node]][l] < elem[Right[node]][r]) {
elem[node].push_back(elem[Left[node]][l]);
++l;
}
else {
elem[node].push_back(elem[Right[node]][r]);
++r;
}
}
}
inline ll GetAfter(int i , int k , int node = 1 , int lx = 1 , int rx = Size) {
if(rx < k || node == 0) return 1e9;
if(lx >= k) {
auto it = lower_bound(elem[node].begin() , elem[node].end() , i);
if(it == elem[node].end()) return 1e9;
return *it;
}
int mid = (lx + rx) / 2;
return min(GetAfter(i , k , Left[node] , lx , mid) , GetAfter(i , k , Right[node] , mid + 1 , rx));
}
inline ll GetBefore(int i , int k , int node = 1 , int lx = 1 , int rx = Size) {
if(rx < k || node == 0) return 0;
if(lx >= k) {
auto it = upper_bound(elem[node].begin() , elem[node].end() , i);
if(it == elem[node].begin()) return 0;
return *prev(it);
}
int mid = (lx + rx) / 2;
return max(GetBefore(i , k , Left[node] , lx , mid) , GetBefore(i , k , Right[node] , mid + 1 , rx));
}
inline ll GetCount(int l , int r , int k , int node = 1 , int lx = 1 , int rx = Size) {
if(rx < k || node == 0) return 0;
if(lx >= k) {
auto it1 = lower_bound(elem[node].begin() , elem[node].end() , l);
auto it2 = upper_bound(elem[node].begin() , elem[node].end() , r);
return it2 - it1;
}
int mid = (lx + rx) / 2;
return GetCount(l , r , k , Left[node] , lx , mid) + GetCount(l , r , k , Right[node] , mid + 1 , rx);
}
} Tree1 , Tree2 , Tree3;
inline ll GetMax(int l , int r) {
if(r < l) return 0;
int Lg = log2(r - l + 1);
return max(sparse[l][Lg] , sparse[r - (1 << Lg) + 1][Lg]);
}
void init(int N, vector<ll> H) {
n = N;
Tree1.Init();
Tree2.Init();
Tree3.Init();
for(int i = 1 ; i <= n ; ++i) s[i] = H[i - 1];
for(int i = 1 ; i <= n ; ++i) sparse[i][0] = s[i];
for(int j = 1 ; j <= lg ; ++j)
for(int i = 1 ; i <= n ; ++i) {
int After = min(n , i + (1 << (j - 1)));
sparse[i][j] = max(sparse[i][j - 1] , sparse[After][j - 1]);
}
stack<ll>st;
for(int i = 1 ; i <= n ; ++i) {
while(st.size() && s[i] < s[st.top()]) {
Right[st.top()] = i;
st.pop();
}
st.push(i);
}
while(st.size()) {
Right[st.top()] = n + 1;
st.pop();
}
for(int i = n ; i >= 1 ; --i) {
while(st.size() && s[i] < s[st.top()]) {
Left[st.top()] = i;
st.pop();
}
st.push(i);
}
while(st.size()) {
Left[st.top()] = 0;
st.pop();
}
//for(int i = 1 ; i <= n ; ++i) cout << Left[i] << " " << Right[i] << endl;
for(int i = 1 ; i <= n ; ++i) {
int max1 = GetMax(Left[i] + 1 , i - 1);
int max2 = GetMax(i + 1 , Right[i] - 1);
if(max1 > s[i]) {
Tree2.Update(max1 - s[i] , i);
}
if(max2 > s[i]) {
Tree1.Update(max2 - s[i] , i);
}
if(max1 > s[i] && max2 > s[i]) {
Tree3.Update(min(max1 , max2) - s[i] , i);
}
}
Tree1.Build();
Tree2.Build();
Tree3.Build();
}
int max_towers(int L, int R, int D) {
int k = D;
++L , ++R;
int l = Tree1.GetAfter(L , k);
int r = Tree2.GetBefore(r , k);
if(r < l) return 1;
int cnt = Tree3.GetCount(l + 1 , r - 1 , k);
return cnt + 2;
}
Compilation message
towers.cpp: In member function 'void sgtree::Build(int, int, int)':
towers.cpp:38:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:38:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | while(l < elem[Left[node]].size() || r < elem[Right[node]].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:39:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
39 | if(l == elem[Left[node]].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
43 | else if(r == elem[Right[node]].size()) {
| ~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:160:28: warning: 'r' is used uninitialized in this function [-Wuninitialized]
160 | int r = Tree2.GetBefore(r , k);
| ~~~~~~~~~~~~~~~^~~~~~~
/tmp/ccWG7Rvx.o: in function `init(int, std::vector<int, std::allocator<int> >)':
towers.cpp:(.text+0x9d6): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xa1f): relocation truncated to fit: R_X86_64_PC32 against symbol `s' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xa3a): relocation truncated to fit: R_X86_64_PC32 against symbol `s' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xa41): relocation truncated to fit: R_X86_64_PC32 against symbol `sparse' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xa65): relocation truncated to fit: R_X86_64_PC32 against symbol `sparse' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xb8f): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xc06): relocation truncated to fit: R_X86_64_PC32 against symbol `s' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xc12): relocation truncated to fit: R_X86_64_PC32 against symbol `Right' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xd8f): relocation truncated to fit: R_X86_64_PC32 against symbol `n' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xdc5): relocation truncated to fit: R_X86_64_PC32 against symbol `Right' defined in .bss section in /tmp/ccWG7Rvx.o
towers.cpp:(.text+0xe8f): additional relocation overflows omitted from the output
/usr/bin/ld: failed to convert GOTPCREL relocation; relink with --no-relax
collect2: error: ld returned 1 exit status
