結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー yaoshimaxyaoshimax
提出日時 2015-06-23 16:58:17
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 149 ms / 5,000 ms
コード長 3,105 bytes
コンパイル時間 802 ms
コンパイル使用メモリ 78,452 KB
実行使用メモリ 7,720 KB
最終ジャッジ日時 2023-09-22 00:15:53
合計ジャッジ時間 2,890 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
7,520 KB
testcase_01 AC 4 ms
7,524 KB
testcase_02 AC 4 ms
7,588 KB
testcase_03 AC 5 ms
7,512 KB
testcase_04 AC 4 ms
7,720 KB
testcase_05 AC 5 ms
7,524 KB
testcase_06 AC 11 ms
7,576 KB
testcase_07 AC 5 ms
7,456 KB
testcase_08 AC 6 ms
7,492 KB
testcase_09 AC 69 ms
7,516 KB
testcase_10 AC 78 ms
7,584 KB
testcase_11 AC 41 ms
7,452 KB
testcase_12 AC 69 ms
7,452 KB
testcase_13 AC 14 ms
7,568 KB
testcase_14 AC 39 ms
7,452 KB
testcase_15 AC 95 ms
7,524 KB
testcase_16 AC 111 ms
7,524 KB
testcase_17 AC 149 ms
7,584 KB
testcase_18 AC 75 ms
7,512 KB
testcase_19 AC 97 ms
7,576 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;

#define N_MAX (1<<17)
class SegTreeLazy{
   private:
      int val[(2*N_MAX)+1];  // その領域の
      int lazy[(2*N_MAX)+1]; // -1でない時、その領域はすべてlazy[?]で満たされているとする
   public:
   
   SegTreeLazy(){
      for( int i = 0 ; i < (2*N_MAX)+1; i++ ){
         val[i]=0;
         lazy[i]=-1;
      }
   }
   
   inline int evalAll(int v, int l=1, int r=N_MAX+1 ){
      //val[k] が示す[l,r)の範囲には各要素の値としてvのみ入っている。  
      //この場合のval[k]の算出式をここで定義する。
      //大体は総和な気がするけれど、最大値や最小値だった時にはここの値を定義し直す必要がある。
      return (r-l)*v;
   }
   inline int combine( int x, int y ){
      // 二つの範囲の代表値x,yを与えられた時に何を返すか
      // 大体は総和なきがするけど、最大値や最小値だった時には(ry)
      return x+y;
   }
   inline int lazy_eval(int l=1, int r=N_MAX+1, int k=1){
      if( lazy[k]!=-1 ){
         if( k*2+1 <= 2*(N_MAX)+1 ){
            val[k*2]=val[k*2+1]=0;
            lazy[k*2]=lazy[k*2+1]=lazy[k];
         }
         val[k]=evalAll(lazy[k],l,r);
         lazy[k]=-1;
      }
      return val[k];
   }
   int getVal(int x, int y, int l=1, int r=N_MAX+1,int k=1 ){
      //get data in [x,y)
      //val[k]=data in [l,r)
      if( l>=r ) return 0;          // エラー値なので状況次第で変更する。 
      if( y<=l || r<=x ) return 0;  // 同上
      if( x<=l && r<=y ) return lazy_eval(l,r,k);
      lazy_eval(l,r,k);
      int m=(l+r)/2;
      return combine(getVal(x,y,l,m,k*2),getVal(x,y,m,r,k*2+1));
   }
   void fill(int x, int y, int v, int l=1, int r=N_MAX+1,int k=1 ){
      //fill data v in [x,y)
      //val[k]= data in [l,r)
      lazy_eval(l,r,k);
      if( l>= r ) return;
      if( y<=l || r<=x ) return;
      if( x<=l && r<=y ){
         lazy[k]=v;
         lazy_eval(l,r,k);
         return;
      }
      int m=(l+r)/2;
      fill(x,y,v,l,m,k*2);
      fill(x,y,v,m,r,1+k*2);
      val[k]=combine(val[k*2],val[k*2+1]);
   }
   void print(int l=1, int r=N_MAX+1, int k=1){
      cout << l << "-"<<r<<": "<<val[k]<<", "<< lazy[k]<<endl;
      if( l+1 < r ){
         int m=(l+r)/2;
         print(l,m,k*2);
         print(m,r,1+k*2);
      }
   }

};

int main(){
    int N,Q;
    SegTreeLazy seg[2];    
    cin >> N >> Q;
    long long pointA=0;
    long long pointB=0;

    for( int i =0 ; i < Q; i++ ){
      int x,l,r;
      scanf("%d%d%d",&x,&l,&r);
      if( x!=0 ){
         seg[x-1].fill(l+1,r+2,1);
         seg[2-x].fill(l+1,r+2,0);
         //seg[0].print();
      }
      else{
         int numA= seg[0].getVal(l+1,r+2);         
         int numB= seg[1].getVal(l+1,r+2);         
         if( numA > numB) pointA+=numA;
         if( numB > numA) pointB+=numB;
      }
    }
    pointA += seg[0].getVal(1,N+1);
    pointB += seg[1].getVal(1,N+1);
    cout << pointA << " " << pointB<<endl;
    return 0;        
}
0