This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "towers.h"
#include <vector>
#include <numeric>
#include <algorithm>
#include <set>
template<int comb(int,int)>
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] = comb(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] = comb(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;
bool f = 0;
while(l < r)
{
if(l&1) if(f) o = comb(o,data[l++]); else {f=1;o=data[l++];};
if(r&1) if(f) o = comb(o,data[--r]); else {f=1;o=data[--r];};
l>>=1;
r>>=1;
}
return o;
}
};
int add(int a, int b) {return a+b;}
int max(int a, int b) {return std::max(a,b);}
std::vector<int> H;
std::vector<int> m;
SegmentTree<add> st;
SegmentTree<max> m_st;
int mn;
void init(int N, std::vector<int> _H) {
for(auto i : _H)
{
if(H.size() && H.back()==i)
{
m.push_back(H.size()-1);
}
else
{
m.push_back(H.size());
H.push_back(i);
}
}
std::vector<int> minima(H.size());
for(int i = 1; i < H.size()-1;i++)
minima[i] = H[i-1] > H[i] && H[i] < H[i+1];
// annoying if range is 2I1(1112I1)
// WLOG take the leftmost in an equal range
st = decltype(st)(minima);
m_st = decltype(m_st)(H);
for(mn=0;mn+1<N&&H[mn+1]>H[mn];mn++);
}
int ct = 0;
int max_towers(int L, int R, int D) {
L = m[L];
R = m[R];
if(L==R) return 1;
if(D==1)
{
auto a = st.query(L+1,R);
if(L+1 < H.size() && H[L]<H[L+1]) a++;
if(R > 0 && H[R]<H[R-1]) a++;
return a;
}
if(++ct>1)
{
if(L >= mn || R <= mn) return 1;
auto a = H[L];
auto b = H[R];
auto c = H[mn];
if(a <= c-D && b <= c-D) return 2;
return 1;
}
std::vector<int> idx_sorted(H.size());
SegmentTree<max> st(H);
std::iota(idx_sorted.begin(),idx_sorted.end(),0);
std::sort(idx_sorted.begin(),idx_sorted.end(),[](auto a, auto b) {return H[a] < H[b];});
std::set<int> included;
for(auto i : idx_sorted)
{
if(i < L || i > R) continue;
auto p = included.lower_bound(i);
if(p!=included.begin())
{
auto l = *std::prev(p);
l++;
if(l==i) continue;
if (st.query(l,i)-D < H[i]) continue;
}
if(p!=included.end())
{
auto r = *p;
if(r==i+1) continue;
if(st.query(i+1,r)-D < H[i]) continue;
}
// bool inv = false;
// for(auto j : included)
// {
// auto l = std::min(i,j);
// l++;
// auto r = std::max(i,j);
// if(l==r) {inv = true;break;}
// auto c = st.query(l,r);
// if(H[i] > c-D || H[j] > c-D) {inv = true;break;}
// }
included.insert(i);
}
return included.size();
}
/*
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
DONE 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 (stderr)
towers.cpp: In member function 'int SegmentTree<comb>::query(int, int)':
towers.cpp:58:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
58 | if(l&1) if(f) o = comb(o,data[l++]); else {f=1;o=data[l++];};
| ^
towers.cpp:59:15: warning: suggest explicit braces to avoid ambiguous 'else' [-Wdangling-else]
59 | if(r&1) if(f) o = comb(o,data[--r]); else {f=1;o=data[--r];};
| ^
towers.cpp: In function 'void init(int, std::vector<int>)':
towers.cpp:88:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
88 | for(int i = 1; i < H.size()-1;i++)
| ~~^~~~~~~~~~~~
towers.cpp: In function 'int max_towers(int, int, int)':
towers.cpp:104:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
104 | if(L+1 < H.size() && H[L]<H[L+1]) a++;
| ~~~~^~~~~~~~~~
towers.cpp: In instantiation of 'SegmentTree<comb>::SegmentTree(const std::vector<int>&) [with int (* comb)(int, int) = add]':
towers.cpp:92:29: required from here
towers.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
34 | for(int i = 0; i < vec.size(); i++) data[vec.size()+i] = vec[i];
| ~~^~~~~~~~~~~~
towers.cpp: In instantiation of 'SegmentTree<comb>::SegmentTree(const std::vector<int>&) [with int (* comb)(int, int) = max]':
towers.cpp:93:28: required from here
towers.cpp:34:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |