結果

問題 No.1786 Maximum Suffix Median (Online)
コンテスト
ユーザー Nachia
提出日時 2022-02-08 18:31:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 291 ms / 2,000 ms
コード長 5,431 bytes
コンパイル時間 1,249 ms
コンパイル使用メモリ 87,404 KB
最終ジャッジ日時 2025-01-27 20:46:17
ジャッジサーバーID
（参考情報） 		judge1 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <vector>
#include <algorithm>


namespace nachia{

    template<class Elem>
    struct leftist_heap{
        struct Node{
            Node* l;
            Node* r;
            int height;
            Elem key;
        };

        Node* root;
        int m_size;

        leftist_heap(){
            root = nullptr;
            m_size = 0;
        }

        leftist_heap(leftist_heap&& src){
            root = src.root;
            m_size = src.m_size;
            src.root = nullptr;
            src.m_size = 0;
        }

        leftist_heap& operator=(leftist_heap&& src){
            root = src.root;
            m_size = src.m_size;
            src.root = nullptr;
            src.m_size = 0;
            return *this;
        }

        ~leftist_heap(){
            if(root){
                ::std::vector<Node*> p = {root};
                while(p.size()){
                    auto c = p.back(); p.pop_back();
                    if(c->l) p.push_back(c->l);
                    if(c->r) p.push_back(c->r);
                    delete(c);
                }
            }
        }

        static Node* meld_node_norecursive(Node* root, Node* anotherroot){
            if(anotherroot == nullptr){
                return root;
            }
            if(root == nullptr){
                root = anotherroot;
                return root;
            }
            ::std::vector<Node*> st;
            st.reserve(root->height + anotherroot->height);
            Node** p1 = &root;
            Node** p2 = &anotherroot;
            while(true){
                if(*p1 == nullptr){
                    *p1 = *p2;
                    break;
                }
                if((*p1)->key < (*p2)->key) ::std::swap(*p1, *p2);
                st.push_back(*p1);
                p1 = &(*p1)->r;
            }
            auto st_ritr = st.rbegin();
            while(st_ritr != st.rend()){
                Node* c = *st_ritr;
                if(c->l == nullptr){
                    std::swap(c->l, c->r);
                    c->height = 1;
                }
                else if(c->r == nullptr){
                    c->height = 1;
                }
                else{
                    if(c->l->height < c->r->height){
                        ::std::swap(c->l, c->r);
                    }
                    c->height = c->r->height + 1;
                }
                st_ritr++;
            }
            return root;
        }

        void push(const Elem& val){
            Node* new_node = new Node();
            new_node->height = 1;
            new_node->l = nullptr;
            new_node->r = nullptr;
            new_node->key = val;
            root = meld_node_norecursive(root, new_node);
            m_size += 1;
        }

        Elem top(){
            return root->key;
        }

        void pop(){
            auto old_root = root;
            root = meld_node_norecursive(old_root->l, old_root->r);
            delete(old_root);
            m_size -= 1;
        }

        int size(){
            return m_size;
        }

        void meld(leftist_heap& r){
            root = meld_node_norecursive(root, r.root);
            r.root = nullptr;
            r.m_size = 0;
        }
    };

}



#include <algorithm>

struct less_int{
    int a;
    bool operator<(less_int& r) const { return a < r.a; }
};
struct greater_int{
    int a;
    bool operator<(greater_int& r) const { return a > r.a; }
};


struct Block{
    nachia::leftist_heap<less_int> L;
    nachia::leftist_heap<greater_int> R;
    Block() = default;
    Block(Block&& src) = default;
    Block& operator=(Block&& src) = default;
    int mid(int newitem) {
        if(L.top().a > newitem) return L.top().a;
        return newitem;
    }
    static Block make(int l, int r){
        Block res;
        res.L.push(less_int{l});
        res.R.push(greater_int{r});
        return res;
    }
};

Block merge_blocks(Block l, Block r){
    if(l.L.size() < r.L.size()) std::swap(l,r);
    l.L.meld(r.L);
    l.R.meld(r.R);
    int swap_count = 0;
    while(l.L.top().a > l.R.top().a){
        int lL = l.L.top().a; l.L.pop();
        int lR = l.R.top().a; l.R.pop();
        l.L.push(less_int{lR});
        l.R.push(greater_int{lL});
        swap_count++;
    }
    return l;
}

bool have_better_merge(Block& l, Block& r){
    return !(l.R.top().a < r.L.top().a);
}


#include <iostream>
#include <vector>

int main() {
    using namespace std;
    int N; cin >> N;
    vector<int> A(N);
    int preans = 0;

    vector<Block> blocks[2];
    for(int t=0; t<2; t++){
        blocks[t].push_back(Block::make(-2,-2));
    }

    for(int i=0; i<N; i++){
        int a; cin >> a; a ^= preans;
        A[i] = a;
        int t = i%2;
        preans = blocks[1-t].back().mid(a);
        if(i == 0){
            blocks[t].push_back(Block::make(-1,a));
        }
        else{
            Block tmp = Block::make(min(A[i-1], A[i]), max(A[i-1], A[i]));
            while(true){
                if(!have_better_merge(blocks[t].back(), tmp)) break;
                tmp = merge_blocks(move(blocks[t].back()), move(tmp));
                blocks[t].pop_back();
            }
            blocks[t].push_back(move(tmp));
        }
        cout << preans << "\n";
    }
    return 0;
}


struct ios_do_not_sync{
    ios_do_not_sync(){
        std::ios::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
} ios_do_not_sync_instance;
0