結果
問題 | No.1786 Maximum Suffix Median (Online) |
ユーザー |
👑 ![]() |
提出日時 | 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 |
ソースコード
#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;