結果

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

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 AC 2 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 1 ms
5,376 KB
testcase_05 AC 2 ms
5,376 KB
testcase_06 AC 9 ms
5,376 KB
testcase_07 AC 2 ms
5,376 KB
testcase_08 AC 4 ms
5,376 KB
testcase_09 AC 66 ms
5,376 KB
testcase_10 AC 62 ms
5,376 KB
testcase_11 AC 38 ms
5,376 KB
testcase_12 AC 69 ms
5,376 KB
testcase_13 AC 13 ms
5,376 KB
testcase_14 AC 47 ms
7,396 KB
testcase_15 AC 103 ms
7,424 KB
testcase_16 AC 116 ms
7,296 KB
testcase_17 AC 144 ms
7,416 KB
testcase_18 AC 81 ms
7,412 KB
testcase_19 AC 87 ms
7,424 KB
権限があれば一括ダウンロードができます

ソースコード

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