結果
問題 | No.1786 Maximum Suffix Median (Online) |
ユーザー |
👑 ![]() |
提出日時 | 2021-12-15 00:59:26 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 739 ms / 2,000 ms |
コード長 | 5,429 bytes |
コンパイル時間 | 4,794 ms |
コンパイル使用メモリ | 124,552 KB |
最終ジャッジ日時 | 2025-01-26 22:41:10 |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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;}};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{priority_queue<int, vector<int>, less<int>> L;priority_queue<int, vector<int>, greater<int>> R;void output(){auto Lbuf = L;cout << "L : [ "; while(Lbuf.size()){ cout << Lbuf.top() << " "; Lbuf.pop(); } cout << "] ";auto Rbuf = R;cout << "R : [ "; while(Rbuf.size()){ cout << Rbuf.top() << " "; Rbuf.pop(); } cout << "] ";cout << endl;}int mid(int newitem) const {if(L.top() > newitem) return L.top();return newitem;}static Block make(int l, int r){Block res;res.L.push(l);res.R.push(r);return res;}};Block merge_blocks(Block l, Block r){if(l.L.size() < r.L.size()) swap(l,r);while(r.L.size()){l.L.push(r.L.top()); r.L.pop();l.R.push(r.R.top()); r.R.pop();}int swap_count = 0;while(l.L.top() > l.R.top()){int lL = l.L.top(); l.L.pop();int lR = l.R.top(); l.R.pop();l.L.push(lR);l.R.push(lL);swap_count++;}cout << " -> " << l.L.top() << ", " << l.R.top() << endl;return move(l);}bool have_better_merge(Block& l, Block& r){return !(l.R.top() < r.L.top());}*/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);while(r.L.size()){l.L.push(r.L.top()); r.L.pop();l.R.push(r.R.top()); r.R.pop();}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;// cout << "a = " << A[i] << endl;int t = i%2;//auto& pblock = blocks[1-t].back();preans = blocks[1-t].back().mid(a);//if(pblock.L.top() > a) preans = pblock.L.top();//else preans = 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";//cout << "process : " << endl; cout << endl;//rep(t,2){ for(auto& a : blocks[t]) a.output(); cout << endl; }//cout << endl << endl;}return 0;}struct ios_do_not_sync{ios_do_not_sync(){ios::sync_with_stdio(false);cin.tie(nullptr);}} ios_do_not_sync_instance;