結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー ei1333333ei1333333
提出日時 2015-08-30 16:52:10
言語 C++11
(gcc 11.4.0)
結果
WA  
実行時間 -
コード長 3,932 bytes
コンパイル時間 2,025 ms
コンパイル使用メモリ 173,016 KB
実行使用メモリ 173,676 KB
最終ジャッジ日時 2023-09-25 19:49:11
合計ジャッジ時間 7,619 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 WA -
testcase_01 WA -
testcase_02 WA -
testcase_03 WA -
testcase_04 AC 2 ms
4,376 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000000000009LL;


vector< int > nums;

struct SegmentTree
{
  struct node
  {
    vector< long long > Sum;
    int LazyColor, LazySum;
    node():LazyColor(-1), LazySum(0) {
      Sum.assign(5, 0);
    };
  };
  vector< node > seg;
  int sz;

  SegmentTree(int n)
  {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(sz * 2 - 1, node());
  }
  inline void Update(int k, int l, int r)
  {
    l = nums[l], r = nums[r];
    for(int i = 0; i < seg[k].Sum.size(); i++) {
      long long &R = seg[k].Sum[i]; R = 0;
      if(seg[2 * k + 1].LazyColor == -1) R += seg[2 * k + 1].Sum[i];
      else if(seg[2 * k + 1].LazyColor == i) R += ((long long)(l + r) / 2 - l) * seg[2 * k + 1].LazySum;
      if(seg[2 * k + 2].LazyColor == -1) R += seg[2 * k + 2].Sum[i];
      else if(seg[2 * k + 2].LazyColor == i) R += (long long)(r - (l + r) / 2) * seg[2 * k + 2].LazySum;
    }
  }
  inline void Evaluation(int k, int l, int r)
  {
    if(seg[k].LazyColor == -1) return;
    if(k < sz - 1) {
      if(seg[2 * k + 1].LazyColor == seg[k].LazyColor) seg[2 * k + 1].LazySum += seg[k].LazySum;
      else  seg[2 * k + 1].LazyColor = seg[k].LazyColor, seg[2 * k + 1].LazySum = seg[k].LazySum;
      if(seg[2 * k + 2].LazyColor == seg[k].LazyColor) seg[2 * k + 2].LazySum += seg[k].LazySum;
      else seg[2 * k + 2].LazyColor = seg[k].LazyColor, seg[2 * k + 2].LazySum = seg[k].LazySum;
      Update(k, l, r);
    } else {
      for(int i = 0; i < seg[k].Sum.size(); i++) {
        seg[k].Sum[i] = (seg[k].LazyColor == i) * seg[k].LazySum;
      }
    }
    seg[k].LazyColor = -1;
    seg[k].LazySum   = 0;
  }

  inline void Write(int a, int b, int x, int k, int l, int r)
  {
    Evaluation(k, l, r);
    if(a >= r || b <= l) return;
    if(a <= l && r <= b) {
      if(seg[k].LazyColor == x) seg[k].LazySum++;
      else seg[k].LazyColor = x, seg[k].LazySum = 1;
      Evaluation(k, l, r);
    } else {
      Write(a, b, x, 2 * k + 1, l, l + r >> 1);
      Write(a, b, x, 2 * k + 2, l + r >> 1, r);
      Update(k, l, r);
    }
  }
  inline void Write(int a, int b, int k)
  {
    Write(a, b, k, 0, 0, sz);
  }
  inline vector< long long > CountSum(int a, int b, int k, int l, int r)
  {
    Evaluation(k, l, r);
    if(a >= r || b <= l) return(vector< long long >(5, 0LL));
    if(a <= l && r <= b) return(seg[k].Sum);
    vector< long long > L = CountSum(a, b, 2 * k + 1, l, l + r >> 1);
    vector< long long > R = CountSum(a, b, 2 * k + 2, l + r >> 1, r);
    for(int i = 0; i < L.size(); i++) L[i] += R[i];
    return(L);
  }
  inline vector< long long > CountSum(int a, int b)
  {
    return(CountSum(a, b, 0, 0, sz));
  }
};

int x[150000];
long long l[150000], r[150000];

int main()
{
  int N, Q;
  scanf("%d", &N);
  scanf("%d", &Q);

  long long P[5] = {};

  for(int i = 0; i < Q; i++) {
    scanf("%d %lld %lld", &x[i], &l[i], &r[i]);
    nums.push_back(l[i] - 1);
    nums.push_back(l[i]);
    nums.push_back(l[i] + 1);
    nums.push_back(r[i] - 1);
    nums.push_back(r[i]);
    nums.push_back(r[i] + 1);
  }
  sort(nums.begin(), nums.end());
  nums.erase(unique(nums.begin(), nums.end()), nums.end());

  SegmentTree seg(nums.size());

  for(int i = 0; i < Q; i++) {
    l[i] = lower_bound(nums.begin(), nums.end(), l[i]) - nums.begin();
    r[i] = lower_bound(nums.begin(), nums.end(), r[i]) - nums.begin();
    if(x[i] == 0) {
      vector< long long > Sum = seg.CountSum(l[i], r[i] + 1);
      vector< long long >::iterator Max = max_element(Sum.begin(), Sum.end());
      if(count(Sum.begin(), Sum.end(), *Max) == 1) {
        (P[Max - Sum.begin()] += *Max) %= MOD;
      }
    } else if(x[i] >= 1) {
      seg.Write(l[i], r[i] + 1, x[i] - 1);
    }
  }
  vector< long long > Sum = seg.CountSum(0, nums.size());
  for(int i = 0; i < 5; i++) {
    (P[i] += Sum[i]) %= MOD;
    if(i > 0) putchar(' ');
    printf("%lld", P[i]);
  }
  putchar('\n');
}
0