結果

問題 No.1786 Maximum Suffix Median (Online)
ユーザー 👑 NachiaNachia
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0