結果

問題 No.1786 Maximum Suffix Median (Online)
ユーザー 👑 Nachia
提出日時 2021-12-15 00:37:03
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,397 bytes
コンパイル時間 4,143 ms
コンパイル使用メモリ 123,504 KB
最終ジャッジ日時 2025-01-26 22:40:56
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 21 TLE * 9
権限があれば一括ダウンロードができます

ソースコード

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++)
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;
}
};
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();
}
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);
}
return move(l);
}
int main() {
int N; cin >> N;
vector<int> A(N);
int preans = 0;
vector<Block> blocks[2];
rep(t,2){
Block a;
a.L.push(-2);
a.R.push(-2);
blocks[t].push_back(move(a));
}
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();
if(pblock.L.top() > a) preans = pblock.L.top();
else preans = a;
if(i == 0){
Block tmp;
tmp.L.push(-1);
tmp.R.push(a);
blocks[t].push_back(move(tmp));
}
else{
Block tmp;
tmp.L.push(min(A[i-1], A[i]));
tmp.R.push(max(A[i-1], A[i]));
while(true){
if(blocks[t].back().R.top() < tmp.L.top()) 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