結果

問題 No.255 Splarrraaay ｽﾌﾟﾗｰﾚｪｰｰｲ
ユーザー pekempeypekempey
提出日時 2016-10-29 12:09:39
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 334 ms / 10,000 ms
コード長 3,439 bytes
コンパイル時間 1,919 ms
コンパイル使用メモリ 175,620 KB
実行使用メモリ 61,056 KB
最終ジャッジ日時 2024-05-03 15:42:29
合計ジャッジ時間 5,883 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 334 ms
60,800 KB
testcase_01 AC 321 ms
60,800 KB
testcase_02 AC 300 ms
60,928 KB
testcase_03 AC 246 ms
60,800 KB
testcase_04 AC 13 ms
36,224 KB
testcase_05 AC 308 ms
60,800 KB
testcase_06 AC 298 ms
61,056 KB
testcase_07 AC 306 ms
60,928 KB
testcase_08 AC 322 ms
60,928 KB
testcase_09 AC 322 ms
60,800 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:135:44: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
  135 |     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

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")

#include <bits/stdc++.h>

#define getchar getchar_unlocked
#define putchar putchar_unlocked

int64_t in() {
    int64_t n;
    int c;
    while ((c = getchar()) < '0') if (c == EOF) return -1;
    n = c - '0';
    while ((c = getchar()) >= '0') n = n * 10 + c - '0';
    return n;
}

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) {
    l += N; r += N;
    int X = l & -l;
    int Y = r & -r;
    int ll = l / X;
    int rr = r / Y - 1;
    push_sup(l, r - 1);
    for (; l < r; l >>= 1, r >>= 1) {
        if (l & 1) set_lazy(l++, c, 1, false);
        if (r & 1) set_lazy(--r, c, 1, false);
    }
    if (X > Y) std::swap(X, Y), std::swap(ll, rr);
    for (; X < Y; X <<= 1, ll >>= 1) fix(ll >> 1);
    for (; ll != rr; ll >>= 1, rr >>= 1) {
        fix(ll >> 1);
        fix(rr >> 1);
    }
    for (; ll > 1; ll >>= 1) fix(ll >> 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);
    }
}

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