Codeforces Global Round 5 D問題 - Balanced Playlist

Source

Codeforces Global Round 5 D問題 (2000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20191108-1）のコード

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

//no-unlocked
int N, A[1d5];
int res[1d5];

int val[1d5], ind[1d5];
int up[1d5], dw[1d5];

{
  int i, j, k, m, mx, mn;
  set<int> s;

  rd(N,A(N));
  mx = max(A(N));
  mn = min(A(N));
  if(mx > 2*mn){
    rep(i,N) ind[i] = i, val[i] = A[i];
    sortA(N, val, ind);
    rrep(k,N){
      i = ind[k];
      s.insert(i);
      s.insert(i + N);
      j = *(s.upper_bound(i));
      if[j == i+N, up[i] = -1, up[i] = j - i];
    }
    s.clear();

    j = 0;
    rep(k,N){
      i = ind[k];
      while(j < N && 2 * val[j] < A[i]){
        s.insert(ind[j]);
        s.insert(ind[j] + N);
        j++;
      }
      if(s.size()==0) dw[i] = -1, continue;
      m = *(s.upper_bound(i));
      dw[i] = m - i;
    }

    rep(i,N) res[i] = int_inf;
    rep(i,N) if(dw[i] != -1) res[i] <?= dw[i];
    rep(k,3) rrep(i,N) if(up[i] != -1) res[i] <?= res[(i+up[i])%N] + up[i];
  } else {
    rep(i,N) res[i] = -1;
  }
  wt(res(N));
}

Current time: 2024年04月20日06時42分30秒
Last modified: 2019年11月10日19時11分33秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces Codeforces_Global_Round_5
トップページに戻る

Logged in as: unknown user (not login)