結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー ikd
提出日時 2018-05-30 05:57:31
言語 D
(dmd 2.109.1)
結果
AC  
実行時間 565 ms / 5,000 ms
コード長 1,799 bytes
コンパイル時間 853 ms
コンパイル使用メモリ 98,944 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-13 01:05:35
合計ジャッジ時間 5,195 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

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 update(int ql, int qr, int x){
    foreach(k; 0..D){
      int l=k*D, r=(k+1)*D;
      if(r<=ql || qr<=l){
        // 
      }else if(ql<=l && r<=qr){
        buc[k]=x*D;
        laz[k]=x;
      }else{
        push(k);
        foreach(i; max(l, ql)..min(r, qr)){
          buc[k]-=val[i];
          val[i]=x;
          buc[k]+=x;
        }        
      }
    }
  }

  int sum(int ql, int qr){
    int ret=0;
    foreach(k; 0..D){
      int l=k*D, r=(k+1)*D;
      if(r<=ql || qr<=l){
        // 
      }else if(ql<=l && r<=qr){
        ret+=buc[k];
      }else{
        push(k);
        foreach(i; max(l, ql)..min(r, qr)) ret+=val[i];
      }
    }
    return ret;
  }

  void push(int k){
    if(laz[k]<0) return;
    val[(k*D)..((k+1)*D)]=laz[k];
    laz[k]=-1;
  }
}

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