結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー sndtkrhsndtkrh
提出日時 2015-12-26 18:40:07
言語 C++11
(gcc 11.4.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 1 ms
6,940 KB
testcase_02 AC 2 ms
6,948 KB
testcase_03 AC 1 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 9 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 76 ms
6,944 KB
testcase_10 AC 80 ms
6,944 KB
testcase_11 AC 44 ms
6,944 KB
testcase_12 AC 75 ms
6,944 KB
testcase_13 AC 12 ms
6,940 KB
testcase_14 AC 81 ms
6,948 KB
testcase_15 AC 119 ms
6,940 KB
testcase_16 AC 137 ms
6,944 KB
testcase_17 AC 161 ms
6,940 KB
testcase_18 AC 107 ms
6,944 KB
testcase_19 AC 91 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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