結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー sndtkrh
提出日時 2015-12-26 18:40:07
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 161 ms / 5,000 ms
コード長 2,682 bytes
コンパイル時間 667 ms
コンパイル使用メモリ 69,184 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-09-19 00:36:04
合計ジャッジ時間 2,600 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef pair<int, int> P;
#define fi first
#define se second
const char A = 0;
const char B = 1;
class Spl{
public:
  P dflt;
  char lazy_dflt;
  Spl(){
    dflt = P(0,0);
    lazy_dflt = -1;
  }
  void lazy_eval(P &tree, char lazy, int l, int r){
    if( lazy == A ){
      tree.fi = r - l;
      tree.se = 0;
    }else if( lazy == B ){
      tree.fi = 0;
      tree.se = r - l;
    }
  }
  void lazy(char &pre_lazy, char lazy){
    if ( lazy == -1 ) return;
    pre_lazy = lazy;
  }
  P marge(P l, P r){
    return P(l.fi + r.fi, l.se + r.se);
  }
};

template <typename T, typename Tlazy, typename Updater>
class LazySegmentTree{
  int N;
  vector<  T  > tree;
  vector<Tlazy> lazy;
  Updater updater;
public:
  LazySegmentTree(){;}
  LazySegmentTree(int n, Updater f) : updater(f) {
    N = 1;
    while(N < n) N *= 2;
    tree.resize( 2 * N - 1, updater.dflt);
    lazy.resize( 2 * N - 1, updater.lazy_dflt);
  }
  inline void lazy_eval_node(int k, int l, int r){
    updater.lazy_eval(tree[k], lazy[k], l, r);
    if ( k < N - 1 ){
      updater.lazy( lazy[2 * k + 1], lazy[k] );
      updater.lazy( lazy[2 * k + 2], lazy[k] );
    }
    lazy[k] = updater.lazy_dflt;
  }
  inline void update_node(int k){
    tree[k] = updater.marge( tree[ 2 * k + 1 ], tree[ 2 * k + 2 ] );
  }
  void update(int a, int b, Tlazy v, int k, int l, int r){
    lazy_eval_node(k, l, r);
    if( b <= l || r <= a ) return;
    if( a <= l && r <= b ){
      updater.lazy( lazy[k], v);
      lazy_eval_node(k, l, r);
      return;
    }
    update(a, b, v, 2 * k + 1, l, (r + l) / 2);
    update(a, b, v, 2 * k + 2, (r + l) / 2, r);
    update_node(k);
  }
  void update(int a, int b, Tlazy v){ update(a, b, v, 0, 0, N); }

  T query(int a, int b, int k, int l, int r){
    lazy_eval_node(k, l, r);
    if( b <= l || r <= a) return updater.dflt;
    if( a <= l && r <= b) return tree[k];
    T lv = query(a,b, 2*k+1, l, (l+r)/2 );
    T rv = query(a,b, 2*k+2, (l+r)/2, r );
    update_node(k);
    return updater.marge(lv, rv);
  }
  T query(int a, int b){ return query(a, b, 0, 0, N); }
};

int main(){
  int N, Q;
  cin >> N >> Q;
  LazySegmentTree<P, char, Spl> lst(N, Spl() );
  long long sa = 0, sb = 0;
  for(int i = 0; i < Q; i++){
    int x, l, r;
    cin >> x >> l >> r;
    if( x == 0 ){
      P p = lst.query(l,r + 1);
      if( p.fi > p.se ){
	sa += p.fi;
      }else if( p.se > p.fi ){
	sb += p.se;
      }
    }else if( x == 1 ){
      lst.update( l, r + 1, A );
    }else{
      lst.update( l, r + 1, B );
    }
  }
  P p = lst.query(0, N);
  sa += p.fi;
  sb += p.se;
  cout << sa << " " << sb << endl;
}
0