結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
ユーザー sndtkrhsndtkrh
提出日時 2015-12-26 18:34:41
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,474 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 69,488 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-19 00:35:56
合計ジャッジ時間 3,553 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,812 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 1 ms
6,940 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 10 ms
6,944 KB
testcase_07 AC 3 ms
6,940 KB
testcase_08 AC 4 ms
6,940 KB
testcase_09 AC 73 ms
6,944 KB
testcase_10 AC 80 ms
6,944 KB
testcase_11 AC 43 ms
6,940 KB
testcase_12 AC 74 ms
6,940 KB
testcase_13 AC 13 ms
6,944 KB
testcase_14 WA -
testcase_15 WA -
testcase_16 AC 135 ms
6,940 KB
testcase_17 AC 157 ms
6,944 KB
testcase_18 AC 110 ms
6,940 KB
testcase_19 AC 89 ms
6,940 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){
    //    cout << "update_node k=" << k << endl;
    tree[k] = updater.marge( tree[ 2 * k + 1 ], tree[ 2 * k + 2 ] );
    //    cout << " " << tree[2*k+1].fi <<"," <<tree[2*k+1].se << " " << tree[2*k+2].fi <<"," <<tree[2*k+2].se << " -> " << tree[k].fi << "," << tree[k].se << endl;
  }
  void update(int a, int b, Tlazy v, int k, int l, int r){
    //    cout << " a=" << a << " b=" << b << " v=" << (int)v << " k=" << k << " l=" << l << " r=" << r << endl;
    //    print();
    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); }


  // 木を表示する
  void print(){
    cout << "print" << endl;
    int p = 1;
    for(int i = 0; i < 2 * N - 1 ; i++){
      if(i+1 >= p){
	p *= 2;
	cerr << endl;
      }
      char p = '_';
      if( lazy[i] == A ) p = 'A';
      if( lazy[i] == B ) p = 'B';
      cerr << "[(" << tree[i].fi << "," << tree[i].se << ")," << p << "] ";
    }
    cerr << endl;
  }

};

int main(){
  int N, Q;
  cin >> N >> Q;
  LazySegmentTree<P, char, Spl> lst(N, Spl() );
  int 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 );
    }
    //    lst.print();
    //    cout << "!!!!!!!!!!!!!!!!!!!!!!!!!!!" << endl;
  }
  P p = lst.query(0, N);
  sa += p.fi;
  sb += p.se;
  cout << sa << " " << sb << endl;
}
0