# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
975273 | 2024-05-04T16:31:11 Z | canadavid1 | Editor (BOI15_edi) | C++14 | 173 ms | 22184 KB |
#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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 173 ms | 22184 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 79 ms | 11624 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 1 ms | 344 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |