結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー yaoshimax
提出日時 2015-06-23 16:58:17
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 119 ms / 5,000 ms
コード長 3,105 bytes
コンパイル時間 690 ms
コンパイル使用メモリ 62,136 KB
実行使用メモリ 7,680 KB
最終ジャッジ日時 2024-07-07 17:11:19
合計ジャッジ時間 2,279 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:88:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   88 |       scanf("%d%d%d",&x,&l,&r);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~

ソースコード

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