結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー yaoshimax
提出日時 2015-06-23 10:40:08
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
TLE  
実行時間 -
コード長 2,293 bytes
コンパイル時間 1,091 ms
コンパイル使用メモリ 59,112 KB
実行使用メモリ 12,264 KB
最終ジャッジ日時 2024-07-07 17:06:36
合計ジャッジ時間 13,101 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 7 TLE * 1 -- * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:76:9: warning: ‘N’ is used uninitialized [-Wuninitialized]
   76 |     init(N);
      |     ~~~~^~~
main.cpp:75:9: note: ‘N’ declared here
   75 |     int N,Q;
      |         ^

ソースコード

diff # 

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

#define N_MAX 1<<17

typedef struct node{
   int numA;
   int numB;
   int lazy;
}node;

node seg[1+(4*N_MAX)];

void init(int n){
   for(int i=0;i<=4*n;i++) seg[i]={0,0,0};
}

void lazy_eval(int l,int r, int k){
   if( seg[k].lazy != 0 ){
      if( seg[k].lazy == 1 ){ seg[k].numA=(r-l+1), seg[k].numB=0;}
      if( seg[k].lazy == 2 ){ seg[k].numB=(r-l+1), seg[k].numA=0;}
      seg[2*k].lazy=seg[k].lazy;
      seg[2*k+1].lazy=seg[k].lazy;
      seg[k].lazy=0;
   }
}

int getVal(int x, int y, int v, int l=1, int r=N_MAX, int k=1){
   //cout << x << ", "<< y <<", "<< v<<", "<< l <<", "<< r<<" ," << k<<endl;
   lazy_eval(l,r,k);
   if( x>r ) return 0;
   if( y<l ) return 0;
   if( x<=l && r <= y ){
      if( v == 1 ) return seg[k].numA;
      if( v == 2 ) return seg[k].numB;
   }
   int m=(l+r)/2;     
   return getVal(x,y,v,l,m,k*2)+getVal(x,y,v,m+1,r,k*2+1);
}
void update(int x,int y, int v, int l=1, int r=N_MAX, int k=1 ){
   lazy_eval(l,r,k);
   if( x>r ) return;
   if( y<l ) return;
   if( x<=l && r <= y ){
      if(v==1){
         seg[k]={r-l+1,0,0};
         seg[2*k].lazy=1;
         seg[2*k+1].lazy=1;
      }
      else{
         seg[k]={0,r-l+1,0};
         seg[2*k].lazy=2;
         seg[2*k+1].lazy=2;
      }
      return;
   }
   int m = (l+r)/2;
   update(x,y,v,l,m,k*2);
   update(x,y,v,m+1,r,k*2+1);
   seg[k].numA=seg[k*2].numA+seg[k*2+1].numA;
   seg[k].numB=seg[k*2].numB+seg[k*2+1].numB;
}
void print(int l=1, int r=N_MAX, int k=1){
   //cout << l <<"-"<< r <<": "<< seg[k].numA<<", "<< seg[k].numB<<", "<< seg[k].lazy << endl;  
   if( l < r ){
      int m=(l+r)/2;
      print( l, m, k*2);
      print( m+1, r, k*2+1);
   }
   
}

int main(){
    int N,Q;
    init(N);
    cin >> N >> Q;
    int pointA=0;
    int pointB=0;
    for( int i =0 ; i < Q; i++ ){
      int x,l,r;
      cin >> x >> l >> r;
      if( x!=0 ){
         update(l+1,r+1,x);
         print();
      }
      else{
         int numA= getVal(l+1,r+1,1);         
         int numB= getVal(l+1,r+1,2);         
         if( numA > numB) pointA+=numA;
         if( numB > numA) pointB+=numB;
      }
    }
    pointA += getVal(1,N,1);
    pointB += getVal(1,N,2);
    cout << pointA << " " << pointB<<endl;
    return 0;        
}
0