Codeforces Round #668 DIV1 C問題/DIV2 E問題 - Fixed Point Removal

Source

Codeforces Round #668 DIV1 C問題 (1500pt)
Codeforces Round #668 DIV2 E問題 (3000pt)
Problem description

問題概要

省略

解法

省略

cLay（version 20200916-1）のコード

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)