結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー SSRSSSRS
提出日時 2022-01-07 12:05:55
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 880 ms / 10,000 ms
コード長 5,044 bytes
コンパイル時間 2,364 ms
コンパイル使用メモリ 185,308 KB
実行使用メモリ 68,420 KB
最終ジャッジ日時 2024-11-08 23:15:21
合計ジャッジ時間 12,490 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 869 ms
68,288 KB
testcase_01 AC 880 ms
68,292 KB
testcase_02 AC 857 ms
68,288 KB
testcase_03 AC 670 ms
68,288 KB
testcase_04 AC 2 ms
5,248 KB
testcase_05 AC 838 ms
68,416 KB
testcase_06 AC 826 ms
68,416 KB
testcase_07 AC 834 ms
68,420 KB
testcase_08 AC 836 ms
68,292 KB
testcase_09 AC 836 ms
68,420 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000000000000009;
struct lazy_segment_tree{
  int N;
  vector<long long> sz;
  vector<array<long long, 5>> sum;
  vector<int> lazy_color, lazy_cnt;
  vector<bool> same;
  lazy_segment_tree(vector<long long> &A){
    int N2 = A.size();
    N = 1;
    while (N < N2){
      N *= 2;
    }
    sz = vector<long long>(N * 2 - 1, 0);
    for (int i = 0; i < N2; i++){
      sz[N - 1 + i] = A[i];
    }
    for (int i = N - 2; i >= 0; i--){
      sz[i] = sz[i * 2 + 1] + sz[i * 2 + 2];
    }
    sum = vector<array<long long, 5>>(N * 2 - 1);
    for (int i = 0; i < N * 2 - 1; i++){
      for (int j = 0; j < 5; j++){
        sum[i][j] = 0;
      }
    }
    lazy_color = vector<int>(N * 2 - 1, -1);
    lazy_cnt = vector<int>(N * 2 - 1, 0);
    same = vector<bool>(N * 2 - 1, true);
  }
  void push(int i){
    if (lazy_color[i] != -1){
      if (i < N - 1){
        if ((lazy_color[i * 2 + 1] == lazy_color[i] || lazy_color[i * 2 + 1] == -1) && same[i]){
          lazy_color[i * 2 + 1] = lazy_color[i];
          lazy_cnt[i * 2 + 1] += lazy_cnt[i];
        } else {
          lazy_color[i * 2 + 1] = lazy_color[i];
          lazy_cnt[i * 2 + 1] = lazy_cnt[i];
          same[i * 2 + 1] = false;
        }
        if ((lazy_color[i * 2 + 2] == lazy_color[i] || lazy_color[i * 2 + 2] == -1) && same[i]){
          lazy_color[i * 2 + 2] = lazy_color[i];
          lazy_cnt[i * 2 + 2] += lazy_cnt[i];
        } else {
          lazy_color[i * 2 + 2] = lazy_color[i];
          lazy_cnt[i * 2 + 2] = lazy_cnt[i];
          same[i * 2 + 2] = false;
        }
      }
      if (!same[i]){
        sum[i][lazy_color[i]] = 0;
      }
      sum[i][lazy_color[i]] += sz[i] * lazy_cnt[i];
      for (int j = 0; j < 5; j++){
        if (j != lazy_color[i]){
          sum[i][j] = 0;
        }
      }
      lazy_color[i] = -1;
      lazy_cnt[i] = 0;
      same[i] = true;
    }
  }
  void range_apply(int L, int R, int x, int i, int l, int r){
    push(i);
    if (r <= L || R <= l){
    } else if (L <= l && r <= R){
      lazy_color[i] = x;
      lazy_cnt[i] = 1;
      same[i] = true;
      push(i);
    } else {
      int m = (l + r) / 2;
      range_apply(L, R, x, i * 2 + 1, l, m);
      range_apply(L, R, x, i * 2 + 2, m, r);
      for (int j = 0; j < 5; j++){
        sum[i][j] = sum[i * 2 + 1][j] + sum[i * 2 + 2][j];
      }
    }
  }
  void range_apply(int L, int R, int x){
    range_apply(L, R, x, 0, 0, N);
  }
  array<long long, 5> range_sum(int L, int R, int i, int l, int r){
    if (r <= L || R <= l){
      array<long long, 5> res;
      for (int j = 0; j < 5; j++){
        res[j] = 0;
      }
      return res;
    } else if (L <= l && r <= R){
      push(i);
      return sum[i];
    } else {
      push(i);
      int m = (l + r) / 2;
      array<long long, 5> A = range_sum(L, R, i * 2 + 1, l, m);
      array<long long, 5> B = range_sum(L, R, i * 2 + 2, m, r);
      for (int j = 0; j < 5; j++){
        A[j] += B[j];
      }
      return A;
    }
  }
  array<long long, 5> range_sum(int L, int R){
    return range_sum(L, R, 0, 0, N);
  }
  array<long long, 5> all_sum(){
    push(0);
    return sum[0];
  }
};
int main(){
  long long N;
  cin >> N;
  int Q;
  cin >> Q;
  vector<int> x(Q);
  vector<long long> l(Q), r(Q);
  for (int i = 0; i < Q; i++){
    cin >> x[i] >> l[i] >> r[i];
    r[i]++;
  }
  vector<long long> X;
  X.push_back(0);
  X.push_back(N);
  for (int i = 0; i < Q; i++){
    X.push_back(l[i]);
    X.push_back(r[i]);
  }
  sort(X.begin(), X.end());
  X.erase(unique(X.begin(), X.end()), X.end());
  int cnt = X.size();
  for (int i = 0; i < Q; i++){
    l[i] = lower_bound(X.begin(), X.end(), l[i]) - X.begin();
    r[i] = lower_bound(X.begin(), X.end(), r[i]) - X.begin();
  }
  vector<long long> w(cnt - 1);
  for (int i = 0; i < cnt - 1; i++){
    w[i] = X[i + 1] - X[i];
  }
  lazy_segment_tree ST(w);
  array<long long, 5> sum;
  for (int i = 0; i < 5; i++){
    sum[i] = 0;
  }
  for (int i = 0; i < Q; i++){
    if (x[i] == 0){
      array<long long, 5> res = ST.range_sum(l[i], r[i]);
      long long mx = 0;
      for (int j = 0; j < 5; j++){
        mx = max(mx, res[j]);
      }
      int mxcnt = 0;
      for (int j = 0; j < 5; j++){
        if (res[j] == mx){
          mxcnt++;
        }
      }
      if (mxcnt == 1){
        for (int j = 0; j < 5; j++){
          if (res[j] == mx){
            sum[j] += res[j];
            sum[j] %= MOD;
          }
        }
      }
    }
    if (x[i] == 1){
      ST.range_apply(l[i], r[i], 0);
    }
    if (x[i] == 2){ 
      ST.range_apply(l[i], r[i], 1);
    }
    if (x[i] == 3){
      ST.range_apply(l[i], r[i], 2);
    }
    if (x[i] == 4){
      ST.range_apply(l[i], r[i], 3);
    }
    if (x[i] == 5){
      ST.range_apply(l[i], r[i], 4);
    }
  }
  array<long long, 5> res = ST.all_sum();
  for (int i = 0; i < 5; i++){
    sum[i] += res[i];
    sum[i] %= MOD;
  }
  for (int i = 0; i < 5; i++){
    cout << sum[i];
    if (i < 4){
      cout << ' ';
    }
  }
  cout << endl;
}
0