結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー okadukiokaduki
提出日時 2016-03-23 15:03:00
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,912 ms / 10,000 ms
コード長 3,734 bytes
コンパイル時間 2,148 ms
コンパイル使用メモリ 188,268 KB
実行使用メモリ 133,332 KB
最終ジャッジ日時 2024-04-20 21:41:27
合計ジャッジ時間 20,886 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,912 ms
133,036 KB
testcase_01 AC 1,854 ms
133,332 KB
testcase_02 AC 1,798 ms
133,168 KB
testcase_03 AC 1,371 ms
132,456 KB
testcase_04 AC 4 ms
11,744 KB
testcase_05 AC 1,772 ms
132,764 KB
testcase_06 AC 1,804 ms
132,884 KB
testcase_07 AC 1,783 ms
132,452 KB
testcase_08 AC 1,777 ms
132,688 KB
testcase_09 AC 1,809 ms
132,084 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const LL MOD = (LL)1e18+9;
int NN;
vector<LL> comp;

struct Node{
  LL dat;
  LL lazy;
  bool zflag;
};
Node segT[5][2*(1<<19)-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 = 0, segT[idx][i].zflag = false;
  }

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

  void update0(int a, int b, 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].zflag = true;
	  eval(k,l,r);
	}
	else{
	  update0(a, b, k*2+1, l, (l+r)/2);
	  update0(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) % MOD;
	}
  }

  // dat[idx] += c, a <= idx < b
  void update(int a, int b, 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++;
	  eval(k,l,r);
	}
	else{
	  update(a, b, k*2+1, l, (l+r)/2);
	  update(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) % MOD;
	}
  }

  LL 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 % MOD;
	else{
	  LL vl = query(a, b, k*2+1, l, (l+r)/2);
	  LL 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) % MOD;
	  return (vl+vr) % MOD;
	}
  }
};

LL N, Q;
void print(vector<LazySegT>& seg){
  cout << "=====" << endl;
  for(int idx=0;idx<5;++idx){
	for(int i=0;i<2*NN-1;++i)
	  cout << seg[idx].query(i,i+1) << " ";
	cout<<endl;
  }
}

int main(){
  cin.tie(0);
  ios_base::sync_with_stdio(false);
  
  cin >> N >> Q;
  vector<tuple<int,LL,LL>> qs(Q);
  {
	for(int q=0;q<Q;++q){
	  int x; LL l, r; cin >> x >> l >> r; ++l, ++r;
	  comp.push_back(l);
	  comp.push_back(r+1);
	  qs[q] = make_tuple(x,l,r+1);
	}
	comp.push_back(0);
	comp.push_back(N+3);
	sort(begin(comp), end(comp));
	comp.erase(unique(begin(comp),end(comp)), end(comp));
	for(int q=0;q<Q;++q){
	  get<1>(qs[q]) = lower_bound(begin(comp), end(comp), get<1>(qs[q])) - begin(comp);
	  get<2>(qs[q]) = lower_bound(begin(comp), end(comp), get<2>(qs[q])) - begin(comp);
	}
	N = comp.size();
  }

  NN = 1;
  while(NN < N) NN <<= 1;
  vector<LazySegT> seg;
  for(int i=0;i<5;++i) seg.emplace_back(i);

  vector<LL> sc(5);
  for(int q=0;q<Q;++q){
	int x; LL l, r;
	tie(x,l,r) = qs[q];
	if(x==0){
	  vector<LL> sum(5);
	  for(int i=0;i<5;++i)
		sum[i] = seg[i].query(l,r);
	  LL mx = *max_element(begin(sum), end(sum));
	  int win = -1;
	  for(int i=0;i<5;++i)
		if(sum[i] == mx){
		  if(win >= 0) win = 10;
		  else win = i;
		}
	  if(win < 5) (sc[win] += mx % MOD) %= MOD;
	}
	else{
	  --x;
	  for(int i=0;i<5;++i)
		if(i == x){
		  seg[i].update(l,r);
		}
		else seg[i].update0(l,r);
	}
  }
  for(int i=0;i<5;++i)
	(sc[i] += seg[i].query(0,N) % MOD) %= MOD;

  for(int i=0;i<5;++i) cout << (i?" ":"") << sc[i];
  cout << endl;

  return 0;
}
0