2019年11月10日19時11分33秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
Codeforces Global Round 5 D問題 (2000pt)
Problem description
省略
省略
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年05月03日07時31分12秒
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)