Submission #979291

#TimeUsernameProblemLanguageResultExecution timeMemory
979291canadavid1Radio Towers (IOI22_towers)C++17
41 / 100
604 ms6528 KiB
#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 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...