#include "towers.h"
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
struct SegmentTree
{
private:
std::vector<int> data;
struct SegTreeReference
{
private:
const int pos;
SegmentTree& t;
public:
SegTreeReference(int pos,SegmentTree& t) : pos(pos), t(t) {}
int operator=(int val)
{
t.assign(pos,val);
return val;
}
operator int() const {return t.data[t.data.size()/2+pos];}
};
public:
SegmentTree() : data(0) {}
SegmentTree(int num) : data(num*2,0) {}
SegmentTree(const std::vector<int>& vec) : data(vec.size()*2)
{
for(int i = 0; i < vec.size(); i++) data[vec.size()+i] = vec[i];
for(int i = vec.size()-1; i > 0; i--)
data[i] = data[2*i]+data[2*i+1];
}
void assign(int pos, int val)
{
data[pos] = val;
pos >>= 1;
for(;pos>0;pos>>=1)
data[pos] = data[2*pos]+data[2*pos+1];
}
SegTreeReference operator[](int pos)
{
return SegTreeReference(pos,*this);
}
int query(int l, int r)
{
l += data.size()/2;
r += data.size()/2;
int o = 0;
while(l < r)
{
if(l&1) o = o+data[l++];
if(r&1) o = o+data[--r];
l>>=1;
r>>=1;
}
return o;
}
};
std::vector<int> H;
std::vector<int> nH;
std::vector<int> map;
SegmentTree st;
void init(int N, std::vector<int> _H) {
H = std::move(_H);
for(auto i : H)
{
if(nH.size() && nH.back()==i)
{
map.push_back(nH.size()-1);
}
else
{
map.push_back(nH.size());
nH.push_back(H[i]);
}
}
std::vector<int> minima(H.size());
for(int i = 1; i < nH.size()-1;i++)
minima[i] = nH[i-1] > nH[i] && nH[i] < nH[i+1];
// annoying if range is 2I1(1112I1)
// WLOG take the leftmost in an equal range
st = decltype(st)(minima);
}
int max_towers(int L, int R, int D) {
L = map[L];
R = map[R];
auto a = st.query(L+1,R);
if(nH[L]<nH[L+1]) a++;
if(nH[R]<nH[R-1]) a++;
return a;
}
/*
WLOG all leased towers are local minima or endpoints
DONE s1: "concave": lease extrema if possible
DONE s2: N <= 1000, Q=1: choose towers from smallest to largest
DONE s23: Q = 1
s4: D = 1
take any which is a local minima
s46: D fixed -> scheduling problem (each tower excludes a certain area)
constrained: won't have ([)] - matched parens
whichever is taller is the outer paren
tree of ranges
s5: L,R is entire range
WLOG use smallest tower
use next smallest that works
need to quickly check if it works (logn time)
or not (subtask 2)
repeat
*/
Compilation message
towers.cpp: In constructor 'SegmentTree::SegmentTree(const std::vector<int>&)':
towers.cpp:31:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for(int i = 0; i < vec.size(); i++) data[vec.size()+i] = vec[i];
| ~~^~~~~~~~~~~~
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:83:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for(int i = 1; i < nH.size()-1;i++)
| ~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
14 ms |
1840 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
5 ms |
868 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
0 ms |
596 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
6 ms |
1368 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
