結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー okaduki
提出日時 2016-03-23 15:03:00
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 2,189 ms / 10,000 ms
コード長 3,734 bytes
コンパイル時間 2,211 ms
コンパイル使用メモリ 189,164 KB
実行使用メモリ 132,136 KB
最終ジャッジ日時 2024-10-12 19:56:10
合計ジャッジ時間 23,438 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 10
権限があれば一括ダウンロードができます

ソースコード

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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0