結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ikdikd
提出日時 2018-05-27 05:17:27
言語 D
(dmd 2.106.1)
結果
AC  
実行時間 732 ms / 5,000 ms
コード長 1,970 bytes
コンパイル時間 1,752 ms
コンパイル使用メモリ 141,832 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-06-13 01:04:53
合計ジャッジ時間 6,991 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 1 ms
6,944 KB
testcase_02 AC 1 ms
6,944 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 15 ms
6,940 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 4 ms
6,944 KB
testcase_09 AC 243 ms
6,940 KB
testcase_10 AC 83 ms
6,940 KB
testcase_11 AC 135 ms
6,944 KB
testcase_12 AC 242 ms
6,940 KB
testcase_13 AC 24 ms
6,944 KB
testcase_14 AC 379 ms
6,940 KB
testcase_15 AC 732 ms
6,944 KB
testcase_16 AC 727 ms
6,944 KB
testcase_17 AC 669 ms
6,940 KB
testcase_18 AC 577 ms
6,944 KB
testcase_19 AC 441 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

void main(){
  import std.stdio, std.string, std.conv, std.algorithm;

  int n; rd(n);
  int q; rd(q);
  long a=0, b=0;
  auto treeA=new SquareRootDecomposition(n),
       treeB=new SquareRootDecomposition(n);
  while(q--){
    int t, l, r; rd(t, l, r);
    if(t==0){
      auto cntA=treeA.sum(l, r+1), cntB=treeB.sum(l, r+1);
      if(cntA==cntB) continue;
      (cntA>cntB ? a : b)+=max(cntA, cntB);
    }else if(t==1){
      treeA.update(l, r+1, 1);
      treeB.update(l, r+1, 0);
    }else if(t==2){
      treeA.update(l, r+1, 0);
      treeB.update(l, r+1, 1);
    }
  }

  a+=treeA.sum(0, n);
  b+=treeB.sum(0, n);
  writeln(a, " ", b);
}

class SquareRootDecomposition{
  import std.algorithm;
  int D=1, nil=-1;
  int[] val, buc, laz;
  this(int n){
    while(D*D<n) D++;
    val.length=D*D;
    buc.length=laz.length=D;
    fill(laz, nil);
  }

  void push(int i){
    if(laz[i]==nil) return;
    val[(i*D)..((i+1)*D)]=laz[i];
    laz[i]=nil;
  }
  int sum(int l, int r){
    int bl=l/D, br=r/D, ret=0;
    if(br-bl<1){
      ret=eachSum(l, r);
    }else{
      ret+=eachSum(l, (bl+1)*D);
      ret+=buc[(bl+1)..br].sum;
      ret+=eachSum(br*D, r);
    }
    return ret;
  }
  int eachSum(int l, int r){
    push(l/D); push(r/D);
    if(l>=r) return 0;
    return val[l..r].sum;
  }
  void update(int l, int r, int x){
    int bl=l/D, br=r/D;
    if(br-bl<1){
      eachUpdate(l, r, x);
    }else{
      eachUpdate(l, (bl+1)*D, x);
      buc[(bl+1)..br]=x*D;
      laz[(bl+1)..br]=x;
      eachUpdate(br*D, r, x);
    }
  }
  void eachUpdate(int l, int r, int x){
    push(l/D); push(r/D);
    foreach(i; l..r){
      buc[i/D]-=val[i];
      val[i]=x;
      buc[i/D]+=val[i];
    }
  }

  void show(){
    import std.stdio;
    writeln(buc);
    writeln(laz);
    writeln(val);
  }
}

void rd(T...)(ref T x){
  import std.stdio, std.string, std.conv;
  auto l=readln.split;
  assert(l.length==x.length);
  foreach(i, ref e; x){
    e=l[i].to!(typeof(e));
  }
}
0