AtCoder Regular Contest 101/AtCoder Beginner Contest 107 D問題 - Median of Medians

Source

AtCoder Regular Contest 101
AtCoder Beginner Contest 107
問題文 (ARC)
問題文 (ABC)

問題概要

省略

解法

省略

cLay（version 20191111-2）のコード

C++に変換後のコードはこちら

int N, A[1d5];
int sm[100001];
{
  ll cnt, all;
  int res;
  fenwick<int> t;

  rd(N,A(N));
  t.malloc(2N+3);

  all = (ll) N * (N+1) / 2;
  res = bsearch_max[int,x,1,1d9][
    t.init(2N+3);
    sm[0] = N;
    rep(i,N) sm[i+1] = sm[i] if[A[i]>=x, +, -] 1;
    cnt = 0;
    rep(i,N+1){
      cnt += t.get(sm[i]);
      t.add(sm[i],1);
    }
  ](2*cnt >= all);
  wt(res);
}

Current time: 2024年04月24日02時16分57秒
Last modified: 2019年11月11日02時44分55秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Regular_Contest AtCoder_Beginner_Contest ARC101 ABC107 ARC_B ABC_D
トップページに戻る

Logged in as: unknown user (not login)