結果

問題 No.230 Splarraay スプラレェーイ
ユーザー yaoshimaxyaoshimax
提出日時 2015-06-23 10:40:08
言語 C++11
(gcc 11.4.0)
結果
TLE  
実行時間 -
コード長 2,293 bytes
コンパイル時間 441 ms
コンパイル使用メモリ 58,444 KB
実行使用メモリ 11,948 KB
最終ジャッジ日時 2023-09-22 00:11:25
合計ジャッジ時間 10,180 ms
ジャッジサーバーID
(参考情報)
judge13 / judge14
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,628 KB
testcase_01 AC 3 ms
5,428 KB
testcase_02 AC 3 ms
5,416 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
5,560 KB
testcase_05 AC 245 ms
5,588 KB
testcase_06 AC 1,463 ms
5,428 KB
testcase_07 AC 269 ms
5,428 KB
testcase_08 AC 638 ms
5,444 KB
testcase_09 TLE -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:76:9: warning: ‘N’ is used uninitialized in this function [-Wuninitialized]
     init(N);
     ~~~~^~~

ソースコード

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