Codeforces Round #668 DIV1 C問題 (1500pt)
Codeforces Round #668 DIV2 E問題 (3000pt)
Problem description
省略
省略
C++に変換後のコードはこちら
//no-unlocked
int N, Q, A[3d5], X[3d5], Y[3d5], ind[3d5], res[3d5];
{
int i, k;
pair<int,int> p;
fenwick<int> f;
segtree<int> t;
rd(N,Q,A(N),(X,Y)(Q));
rep(i,Q) ind[i] = i;
f.walloc(N, 1);
t.walloc(N, 1);
t.change(0, N, int_inf);
sortA(Q, X, Y, ind);
k = N;
rrep(i,Q){
while(k && k-1 >= X[i]){
k--;
if(A[k] > k+1) continue;
t.change(k, k+1, k+1-A[k]);
}
for(;;){
p = t.getMin(0, N);
if(p.first > 0) break;
f.add(p.second, 1);
t.change(p.second, p.second+1, int_inf);
if(p.second+1 < N) t.add(p.second+1, N, -1);
}
res[ind[i]] = f.range(X[i], N-1-Y[i]);
}
rep(i,Q) wt(res[i]);
}
Current time: 2024年04月18日13時08分28秒
Last modified: 2020年09月16日02時37分47秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Codeforces CF668 CF_Div1_C CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)