Submission #975273

#	Time	Username	Problem	Language	Result	Execution time	Memory
975273		canadavid1	Editor (BOI15_edi)	C++14	0 / 100	173 ms	22184 KiB

edi

#include <iostream>
#include <vector>
#include <queue>
#include <set>

template<typename T>
struct ordered
{
    size_t pos;
    T val;
    bool operator<(const ordered& o) const
    {
        if(val<o.val || o.val < val) return val < o.val;
        return pos < o.pos;
    }
};

struct SegmentTree
{
private:
    std::vector<ordered<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].val;}
    };
public:
    SegmentTree() : data(0) {}
    SegmentTree(int num) : data(num*2) {}
    SegmentTree(const std::vector<int>& vec) : data(vec.size()*2)
    {
        
        for(int i = 0; i < vec.size(); i++) data[vec.size()+i].val = vec[i],data[vec.size()+i].pos=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)
    {
        pos += data.size()/2;
        data[pos].val = 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);
    }
    ordered<int> query(int l, int r)
    {
        l += data.size()/2;
        r += data.size()/2;
        ordered<int> o;
        o.val = -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;
    }
};
constexpr int int_min = -(1ll<<31);
int main()
{
    int N;
    std::cin >> N;
    std::vector<int> a(N);
    for(auto& i : a) std::cin >> i;
    SegmentTree level(a);
    SegmentTree exists(N);
    while(level.query(0,N).val>0)
    {
        auto[pos,val] = level.query(0,N);
        auto[pos2,_] = exists.query(0,pos);
        level[pos] = int_min;
        level[pos2] = int_min;
        exists[pos] = -1;
        exists[pos2] = -1;
    }
    for(int i = 0; i < N-1; i++) std::cout << "0\n";
    for(int i = N-1; i >= 0; i--)
    {
        if(level[i]>int_min) {std::cout << -level[i] << "\n";return 0;}
    }

}
/*
    0 1 2  3  4  5
    1 2 -1 -2 -3 -2
    A U A
    A A U  A
    A U A  U  A
    A A U  U  A  A
        1  2  3  2
*/

Compilation message (stderr)

edi.cpp: In constructor 'SegmentTree::SegmentTree(const std::vector<int>&)':
edi.cpp:42:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for(int i = 0; i < vec.size(); i++) data[vec.size()+i].val = vec[i],data[vec.size()+i].pos=i;
      |                        ~~^~~~~~~~~~~~
edi.cpp: In function 'int main()':
edi.cpp:86:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   86 |         auto[pos,val] = level.query(0,N);
      |             ^
edi.cpp:87:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   87 |         auto[pos2,_] = exists.query(0,pos);
      |             ^

• Subtask 1: 0 / 20
• Subtask 2: 0 / 15
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37