結果

問題 No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ
コンテスト
ユーザー okaduki
提出日時 2015-06-21 10:08:38
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 144 ms / 5,000 ms
コード長 2,000 bytes
コンパイル時間 775 ms
コンパイル使用メモリ 56,044 KB
実行使用メモリ 7,424 KB
最終ジャッジ日時 2024-07-07 15:25:43
合計ジャッジ時間 2,016 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>

using namespace std;

typedef long long LL;
int NN;

struct Node{
  int dat;
  int lazy;
};
Node segT[2][2*(1<<17)-1];
/*
	NN = 1;
	while(NN < n_) NN <<= 1;
 */
class LazySegT{
private:
  int idx;
public:
  LazySegT(int idx_){
	idx = idx_;
	for(int i=0;i<2*NN-1;++i) segT[idx][i].dat = 0, segT[idx][i].lazy = -1;
  }

  void eval(int k, int l, int r){
	if(segT[idx][k].lazy < 0) return;
	
	segT[idx][k].dat = segT[idx][k].lazy * (r-l);
	if(k < NN-1){ // not leaf
	  segT[idx][2*k+1].lazy = segT[idx][k].lazy;
	  segT[idx][2*k+2].lazy = segT[idx][k].lazy;
	}
	segT[idx][k].lazy = -1;
  }

  // dat[idx] = c, a <= idx < b
  void update(int a, int b, int c, int k=0, int l=0, int r=NN){
	eval(k,l,r);
	if(r <= a || b <= l) return;

	if(a <= l && r <= b){
	  segT[idx][k].lazy = c;
	  eval(k,l,r);
	}
	else{
	  update(a, b, c, k*2+1, l, (l+r)/2);
	  update(a, b, c, k*2+2, (l+r)/2, r);
	  segT[idx][k].dat = segT[idx][k*2+1].dat + segT[idx][k*2+2].dat;
	}
  }

  int query(int a, int b, int k=0, int l=0, int r=NN){
	eval(k,l,r);
	// no intersect
	if(r <= a || b <= l) return 0;

	// completely contain
	if(a <= l && r <= b) return segT[idx][k].dat;
	else{
	  int vl = query(a, b, k*2+1, l, (l+r)/2);
	  int vr = query(a, b, k*2+2, (l+r)/2, r);
	  segT[idx][k].dat = segT[idx][k*2+1].dat + segT[idx][k*2+2].dat;
	  return vl+vr;
	}
  }
};

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  
  int N, Q; cin >> N >> Q;
  NN = 1;
  while(NN < N) NN <<= 1;
  LazySegT seg1(0), seg2(1);

  LL sc1 = 0, sc2 = 0;
  while(Q--){
	int x, l, r; cin >> x >> l >> r;
	if(x==0){
	  int r1 = seg1.query(l,r+1);
	  int r2 = seg2.query(l,r+1);
	  if(r1 < r2) r1 = 0;
	  else if(r1 > r2) r2 = 0;
	  else r1 = r2 = 0;
	  sc1 += r1;
	  sc2 += r2;
	}
	else if(x==1){
	  seg1.update(l,r+1,1);
	  seg2.update(l,r+1,0);
	}
	else{
	  seg1.update(l,r+1,0);
	  seg2.update(l,r+1,1);
	}
  }
  sc1 += seg1.query(0,N);
  sc2 += seg2.query(0,N);

  cout << sc1 << " " << sc2 << "\n";

  return 0;
}
0