oj.uz

Submission #979146

# Submission time Handle Problem Language Result Execution time Memory
979146 2024-05-10T09:47:57 Z canadavid1 Radio Towers (IOI22_towers) C++17
0 / 100
 419 ms 2608 KB 
#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> rep;
SegmentTree st;
void init(int N, std::vector<int> _H) {
    H = std::move(_H);
    rep.resize(H.size());
    int p=0;
    for(int i = 0; i < rep.size(); i++)
    {
        if(H[p]==H[i]) rep[i] = p;
        else
        {
            p = i;
            rep[i] = 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);
}

int max_towers(int L, int R, int D) {
    auto _L = rep[L]; // take entire range
    auto a = st.query(_L,R+1);
    if(!st.query(R,R+1) && H[R-1] > H[R]) a++;
    if(!st.query(L,L+1) && H[L-1] > H[L]) 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:71:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |     for(int i = 0; i < rep.size(); i++)
      |                    ~~^~~~~~~~~~~~
towers.cpp:82:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |     for(int i = 1; i < H.size()-1;i++)
      |                    ~~^~~~~~~~~~~~

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Incorrect 246 ms 1684 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 419 ms 2608 KB 3rd lines differ - on the 1st token, expected: '14278', found: '14279'
2 Halted 0 ms 0 KB -

Subtask #5
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 172 ms 988 KB 1st lines differ - on the 1st token, expected: '7197', found: '8004'
2 Halted 0 ms 0 KB -

Subtask #6
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB 1st lines differ - on the 1st token, expected: '13', found: '16'
2 Halted 0 ms 0 KB -

Subtask #7
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 246 ms 1684 KB 1st lines differ - on the 1st token, expected: '1', found: '0'
2 Halted 0 ms 0 KB -