結果
問題 |
No.702 中央値を求めよ LIMITED
|
ユーザー |
👑 ![]() |
提出日時 | 2020-10-08 17:57:04 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,466 ms / 5,000 ms |
コード長 | 862 bytes |
コンパイル時間 | 1,579 ms |
コンパイル使用メモリ | 166,860 KB |
実行使用メモリ | 23,040 KB |
最終ジャッジ日時 | 2024-11-22 22:57:47 |
合計ジャッジ時間 | 41,675 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 25 |
ソースコード
#include<bits/stdc++.h> using namespace std; using UL = unsigned int; using LL = long long; using ULL = unsigned long long; #define rep(i,n) for(int i=0; i<(n); i++) UL x=0,y=1,z=2,w=3; UL generate(){ UL t=(x^(x<<11)); x=y; y=z; z=w; w=(w^(w>>19))^(t^(t>>8)); return w; } UL G[5000002]; UL p=0; void push(UL v){ G[p++]=v; UL i=p-1; while(i!=0){ UL to=(i-1)/2; if(G[to]>=G[i]) return; swap(G[to],G[i]); i=to; } } UL top(){ return G[0]; } void pop(){ swap(G[0],G[--p]); int i=0; while(true){ UL to1=i*2+1,to2=i*2+2; UL to=p; if(to2<p){ if(G[i]<max(G[to1],G[to2])) to=(G[to1]>G[to2])?to1:to2; } else if(to1<p){ if(G[i]<G[to1]) to=to1; } if(to==p) return; swap(G[i],G[to]); i=to; } } int main() { cin>>x; rep(i,5000001) push(generate()); rep(i,5000000) push(generate()),pop(); cout<<top()<<endl; return 0; }