Submission #979148

#TimeUsernameProblemLanguageResultExecution timeMemory
979148canadavid1Radio Towers (IOI22_towers)C++17
0 / 100
409 ms3124 KiB
#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> lr; std::vector<int> rr; SegmentTree st; void init(int N, std::vector<int> _H) { H = std::move(_H); lr.resize(H.size()); rr.resize(H.size()); int p=0; for(int i = 0; i < lr.size(); i++) { if(H[p]!=H[i]) p = i; lr[i] = p; } p = rr.size()-1; for(int i = rr.size()-1; i >= 0; i--) { if(H[p]!=H[i]) p = i; lr[i] = p; } std::vector<int> minima(H.size()); for(int i = 1; i < H.size()-1;i++) minima[i] = lr[i] == i && H[i-1]>H[i] && (rr[i]==H.size()-1 || H[rr[i]+1]>H[i]); // 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) { auto a = st.query(rr[L]+1,lr[R]); if(H[lr[R]] < H[lr[R]-1]) a++; if(H[rr[L]] < H[rr[L]+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 (stderr)

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:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0; i < lr.size(); i++)
      |                    ~~^~~~~~~~~~~
towers.cpp:85:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |     for(int i = 1; i < H.size()-1;i++)
      |                    ~~^~~~~~~~~~~~
towers.cpp:86:56: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   86 |         minima[i] = lr[i] == i && H[i-1]>H[i] && (rr[i]==H.size()-1 || H[rr[i]+1]>H[i]);
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...