第二回全国統一プログラミング王決定戦本戦 E問題 - Notorious B.I.T.

Source

第二回全国統一プログラミング王決定戦本戦
問題文

問題概要

省略

解法

省略

cLayversion 20191227-1)のコード

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

int N, M, Q, L[1d5], R[1d5], X;
char S[200002];
set<int> ones;
set<int>::iterator it1, it2;
{
  int i, j, k, res = 0;
  rangeTree2d_nw<int,int> t;
  rd(N,M,Q,S,(L--,R--)(M));
  rep(i,N) S[i] -= '0';
  rep(i,N) if(S[i]) ones.insert(i);
  ones.insert(-1);
  ones.insert(N);
  rep(i,M){
    k = *(ones.lower_bound(L[i]));
    if(k <= R[i]) res++;
  }

  t.build(M, L, R);

  rep(Q){
    rd(X--);
    S[X] ^= 1;
    if(S[X]==1){
      ones.insert(X);
      it1 = it2 = ones.lower_bound(X);
      it1--; it2++;
      res += t.query((*it1)+1, *it2, (*it1)+1, *it2);
      res -= t.query((*it1)+1, X, (*it1)+1, X);
      res -= t.query(X+1, *it2, X+1, *it2);
    } else {
      it1 = it2 = ones.lower_bound(X);
      it1--; it2++;
      ones.erase(X);
      res -= t.query((*it1)+1, *it2, (*it1)+1, *it2);
      res += t.query((*it1)+1, X, (*it1)+1, X);
      res += t.query(X+1, *it2, X+1, *it2);
    }
    wt(res);
  }
}

Current time: 2021年09月25日00時56分52秒
Last modified: 2019年12月27日22時39分02秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder
トップページに戻る

Logged in as: unknown user (not login)

ログイン: