Codeforces Round #694 DIV1 E問題 (2000pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, C, Q, A[3d4], X; ll Y;
ll cnt[5][3d4+2];
int sz, lis[5], ind[5];
int usz[3d4+2], ulis[3d4+2][5];
int dsz[3d4+2], dlis[3d4+2][5];
Arr1d<__int128_t> skip[5];
{
int i, j, k, c;
rep(i,5) cnt[i][0] = 1;
rep(i,5) rep(k,3d4) rep(j,min(k,i)+1){
cnt[i][k+1] += cnt[i-j][k-j];
if(cnt[i][k+1] > 2d18) cnt[i][k+1] = 2d18;
}
REP(rd_int()){
rd(N,C,Q,A(N));
rep(k,N){
sz = 0;
rep(i,C+1) if(k+i < N) arrInsert(sz, sz, ind, i, lis, A[k+i]);
sortA(sz, lis, ind);
j = usz[k] = dsz[k] = 0;
rep(i,sz){
if(ind[i] == 0) j++, continue;
if(j==0) ulis[k][usz[k]++] = ind[i];
if(j==1) dlis[k][dsz[k]++] = ind[i];
}
}
rep(c,C+1){
skip[c].setN(N);
rep(k,N){
skip[c][k] = 0;
rep(i,usz[k]) if(c >= ulis[k][i]) skip[c][k] += cnt[c-ulis[k][i]][N-k-ulis[k][i]-1];
}
}
rep(Q){
rd(X--, Y--);
if(Y >= cnt[C][N]) wt(-1), continue;
c = C;
rep(k,N){
i = bsearch_max[int,i,k-1,N-1](skip[c].getSum(k,i) <= Y < skip[c].getSum(k,i) + cnt[c][N-i-1])+ 1;
if(X < i) wt(A[X]), break;
Y -= skip[c].getSum(k, i-1);
k = i;
rep(i,usz[k]) if(c >= ulis[k][i]){
if(Y < cnt[c-ulis[k][i]][N-k-ulis[k][i]-1]){
if(X <= k + ulis[k][i]) wt(A[k+ulis[k][i]-(X-k)]), break_break;
c -= ulis[k][i];
k += ulis[k][i];
break_continue;
} else {
Y -= cnt[c-ulis[k][i]][N-k-ulis[k][i]-1];
}
}
if(Y < cnt[c][N-k-1]){
if(X == k) wt(A[k]), break;
continue;
} else {
Y -= cnt[c][N-k-1];
}
rep(i,dsz[k]) if(c >= dlis[k][i]){
if(Y < cnt[c-dlis[k][i]][N-k-dlis[k][i]-1]){
if(X <= k + dlis[k][i]) wt(A[k+dlis[k][i]-(X-k)]), break_break;
c -= dlis[k][i];
k += dlis[k][i];
break_continue;
} else {
Y -= cnt[c-dlis[k][i]][N-k-dlis[k][i]-1];
}
}
}
}
}
}
Current time: 2024年04月26日19時30分07秒
Last modified: 2021年01月08日22時28分10秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF694 CF_DIV1_E
トップページに戻る
Logged in as: unknown user (not login)