結果

問題 No.230 Splarraay スプラレェーイ
ユーザー yaoshimax
提出日時 2015-06-23 11:02:19
言語 C++11(廃止可能性あり)
(gcc 13.3.0)
結果
AC  
実行時間 110 ms / 5,000 ms
コード長 2,336 bytes
コンパイル時間 412 ms
コンパイル使用メモリ 58,644 KB
実行使用メモリ 8,724 KB
最終ジャッジ日時 2024-07-07 17:08:51
合計ジャッジ時間 1,743 ms
ジャッジサーバーID
(参考情報)
judge5 / judge1
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:83:12: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   83 |       scanf("%d%d%d",&x,&l,&r);
      |       ~~~~~^~~~~~~~~~~~~~~~~~~
main.cpp:77:9: warning: ‘N’ is used uninitialized [-Wuninitialized]
   77 |     init(N);
      |     ~~~~^~~
main.cpp:76:9: note: ‘N’ declared here
   76 |     int N,Q;
      |         ^

ソースコード

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