Submission #979107

#	Time	Username	Problem	Language	Result	Execution time	Memory
979107		canadavid1	Radio Towers (IOI22_towers)	C++17	23 / 100	4059 ms	4664 KiB

towers

#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] = std::max(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] = std::max(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 = -(1<<31);
        while(l < r)
        {
            if(l&1) o = std::max(o,data[l++]);
            if(r&1) o = std::max(o,data[--r]);
            l>>=1;
            r>>=1;
        }
        return o;
    }
    void push_back(int v)
    {
        int N = data.size()/2;
        data.push_back(data[N]);
        data.push_back(v);
        data[N] = std::max(data[2*N],data[2*N+1]);
    }
    
};

std::vector<int> H;
int m;
void init(int N, std::vector<int> _H) {
    H = std::move(_H);
}

int max_towers(int L, int R, int D) {
    std::vector<int> idx_sorted(H.size());
    SegmentTree 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();
}

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 member function 'int SegmentTree::query(int, int)':
towers.cpp:51:17: warning: integer overflow in expression of type 'int' results in '-2147483648' [-Woverflow]
   51 |         int o = -(1<<31);
      |                 ^~~~~~~~

• Subtask 1: 0 / 4
• Subtask 2: 11 / 11
• Subtask 3: 12 / 12
• Subtask 4: 0 / 14
• Subtask 5: 0 / 17
• Subtask 6: 0 / 19
• Subtask 7: 0 / 23