結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー yaoshimaxyaoshimax
提出日時 2015-06-23 11:02:19
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 127 ms / 5,000 ms
コード長 2,336 bytes
コンパイル時間 433 ms
コンパイル使用メモリ 58,628 KB
実行使用メモリ 9,184 KB
最終ジャッジ日時 2023-09-22 00:13:54
合計ジャッジ時間 2,231 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,544 KB
testcase_01 AC 2 ms
5,560 KB
testcase_02 AC 2 ms
5,540 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 2 ms
5,432 KB
testcase_05 AC 3 ms
5,568 KB
testcase_06 AC 7 ms
5,496 KB
testcase_07 AC 3 ms
5,424 KB
testcase_08 AC 4 ms
5,488 KB
testcase_09 AC 60 ms
7,608 KB
testcase_10 AC 62 ms
5,616 KB
testcase_11 AC 32 ms
6,492 KB
testcase_12 AC 60 ms
8,688 KB
testcase_13 AC 10 ms
5,660 KB
testcase_14 AC 42 ms
4,376 KB
testcase_15 AC 76 ms
7,836 KB
testcase_16 AC 92 ms
8,632 KB
testcase_17 AC 127 ms
8,772 KB
testcase_18 AC 57 ms
9,184 KB
testcase_19 AC 69 ms
8,732 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:77:9: warning: ‘N’ is used uninitialized in this function [-Wuninitialized]
     init(N);
     ~~~~^~~

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <cstdio>
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};
}

inline 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;
    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 ){
         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