結果
問題 | No.1786 Maximum Suffix Median (Online) |
ユーザー |
👑 ![]() |
提出日時 | 2022-01-02 18:57:13 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 234 ms / 2,000 ms |
コード長 | 3,925 bytes |
コンパイル時間 | 2,979 ms |
コンパイル使用メモリ | 124,984 KB |
最終ジャッジ日時 | 2025-01-27 08:28:54 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 30 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <queue>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(n); i++)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;}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;}};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{leftist_heap<less_int> L;leftist_heap<greater_int> R;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()) 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 move(l);}bool have_better_merge(Block& l, Block& r){return !(l.R.top().a < r.L.top().a);}int main() {int N; cin >> N;vector<int> A(N);int preans = 0;vector<Block> blocks[2];rep(t,2){blocks[t].push_back(Block::make(-2,-2));}rep(i,N){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(blocks[t].back(), 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(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;