結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー pekempeypekempey
提出日時 2016-10-29 11:42:36
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 428 ms / 10,000 ms
コード長 3,033 bytes
コンパイル時間 1,518 ms
コンパイル使用メモリ 162,892 KB
実行使用メモリ 61,056 KB
最終ジャッジ日時 2024-11-24 17:44:19
合計ジャッジ時間 6,933 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 428 ms
60,928 KB
testcase_01 AC 428 ms
60,800 KB
testcase_02 AC 407 ms
61,056 KB
testcase_03 AC 334 ms
60,928 KB
testcase_04 AC 15 ms
36,224 KB
testcase_05 AC 413 ms
60,928 KB
testcase_06 AC 408 ms
60,800 KB
testcase_07 AC 410 ms
60,800 KB
testcase_08 AC 408 ms
61,056 KB
testcase_09 AC 411 ms
60,928 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int64_t in()’:
main.cpp:87:15: warning: format ‘%lld’ expects argument of type ‘long long int*’, but argument 2 has type ‘int64_t*’ {aka ‘long int*’} [-Wformat=]
   87 |     scanf("%lld", &t);
      |            ~~~^   ~~
      |               |   |
      |               |   int64_t* {aka long int*}
      |               long long int*
      |            %ld
main.cpp: In function ‘int main()’:
main.cpp:119:44: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
  119 |     for (int i = 0; i < 5; i++) printf("%lld ", (ns[1].sum[i] + sum[i]) % mod);
      |                                         ~~~^    ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      |                                            |                            |
      |                                            long long int                int64_t {aka long int}
      |                                         %ld
main.cpp: In function ‘int64_t in()’:
main.cpp:87:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   87 |     scanf("%lld", &t);
      |     ~~~~~^~~~~~~~~~~~

ソースコード

diff # 

#include <bits/stdc++.h>

struct node {
    int64_t sum[5];
    int64_t w;
    int fill;
    int thick;
    bool reset;
};

const int64_t mod = int64_t(1e18) + 9;
const int H = 19;
const int N = 1 << H;
const int Q = 150000;

int q;
int64_t n, X[Q], L[Q], R[Q], dict[Q * 2], sum[5], result[5];
node ns[N * 2];

void set_lazy(int k, int c, int thick, bool reset) {
    if (ns[k].thick > 0 && ns[k].fill != c) reset = true;
    int64_t s = ns[k].sum[c];
    memset(ns[k].sum, 0, sizeof(ns[k].sum));
    if (reset) {
        ns[k].thick = 0;
        ns[k].reset = true;
        s = 0;
    }
    ns[k].thick += thick;
    ns[k].fill = c;
    ns[k].sum[c] = thick * ns[k].w + s;
}

void push(int k) {
    if (ns[k].thick == 0) return;
    set_lazy(k * 2 + 0, ns[k].fill, ns[k].thick, ns[k].reset);
    set_lazy(k * 2 + 1, ns[k].fill, ns[k].thick, ns[k].reset);
    ns[k].fill = -1;
    ns[k].thick = 0;
    ns[k].reset = false;
}

void fix(int k) {
    for (int i = 0; i < 5; i++) {
        ns[k].sum[i] = ns[k * 2].sum[i] + ns[k * 2 + 1].sum[i];
    }
}

void add(int k) {
    for (int i = 0; i < 5; i++) result[i] += ns[k].sum[i];
}

void push_sup(int l, int r) {
    for (int i = H; i >= 1; i--) {
        push(l >> i);
        push(r >> i);
    }
}

void update(int l, int r, int c) {
    int ll = -1, rr = -1;
    l += N;
    r += N;
    push_sup(l, r - 1);
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) ll = std::max(ll, l), set_lazy(l++, c, 1, false);
        if (r & 1) set_lazy(--r, c, 1, false), rr = std::max(rr, r);
    }
    for (; ll > 1; ll >>= 1) fix(ll >> 1);
    for (; rr > 1; rr >>= 1) fix(rr >> 1);
}


void query(int l, int r) {
    l += N;
    r += N;
    push_sup(l, r - 1);
    memset(result, 0, sizeof(result));
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) add(l++);
        if (r & 1) add(--r);
    }
}

int64_t in() {
    int64_t t;
    scanf("%lld", &t);
    return t;
}

int main() {
    n = in(), q = in();
    for (int i = 0; i < q; i++) {
        X[i] = in() - 1, L[i] = in(), R[i] = in() + 1;
        dict[i * 2 + 0] = L[i];
        dict[i * 2 + 1] = R[i];
    }
    std::sort(dict, dict + q * 2);
    int m = std::unique(dict, dict + q * 2) - dict;
    for (int i = 0; i < m - 1; i++) ns[i + N].w = dict[i + 1] - dict[i];
    for (int i = N - 1; i >= 1; i--) ns[i].w = ns[i * 2].w + ns[i * 2 + 1].w;
    for (int i = 0; i < q; i++) {
        L[i] = std::lower_bound(dict, dict + m, L[i]) - dict;
        R[i] = std::lower_bound(dict, dict + m, R[i]) - dict;
        if (X[i] == -1) {
            query(L[i], R[i]);
            int id = std::max_element(result, result + 5) - result;
            for (int j = 0; j < 5; j++) {
                if (j != id && result[j] == result[id]) {
                    id = -1;
                    break;
                }
            }
            if (id >= 0) (sum[id] += result[id]) %= mod;
        } else {
            update(L[i], R[i], X[i]);
        }
    }
    for (int i = 0; i < 5; i++) printf("%lld ", (ns[1].sum[i] + sum[i]) % mod);
}
0