結果

問題 No.619 CardShuffle
ユーザー くれちーくれちー
提出日時 2017-12-11 18:32:51
言語 C
(gcc 12.3.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 3,536 bytes
コンパイル時間 1,345 ms
コンパイル使用メモリ 30,884 KB
実行使用メモリ 163,540 KB
最終ジャッジ日時 2023-08-24 13:44:13
合計ジャッジ時間 8,389 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,380 KB
testcase_01 AC 0 ms
4,384 KB
testcase_02 AC 1 ms
4,384 KB
testcase_03 AC 0 ms
4,384 KB
testcase_04 AC 1 ms
4,380 KB
testcase_05 AC 0 ms
4,380 KB
testcase_06 AC 1 ms
4,380 KB
testcase_07 AC 1 ms
4,384 KB
testcase_08 AC 1 ms
4,380 KB
testcase_09 AC 1 ms
4,384 KB
testcase_10 AC 1 ms
4,380 KB
testcase_11 AC 0 ms
4,380 KB
testcase_12 AC 0 ms
4,380 KB
testcase_13 AC 1 ms
4,380 KB
testcase_14 AC 0 ms
4,384 KB
testcase_15 AC 1 ms
4,384 KB
testcase_16 AC 302 ms
124,688 KB
testcase_17 AC 270 ms
125,816 KB
testcase_18 AC 277 ms
124,272 KB
testcase_19 AC 278 ms
124,080 KB
testcase_20 AC 276 ms
124,128 KB
testcase_21 AC 374 ms
163,540 KB
testcase_22 AC 340 ms
163,344 KB
testcase_23 AC 352 ms
163,268 KB
testcase_24 AC 343 ms
163,332 KB
testcase_25 AC 336 ms
163,220 KB
testcase_26 AC 205 ms
85,224 KB
testcase_27 AC 201 ms
85,336 KB
testcase_28 AC 207 ms
85,304 KB
testcase_29 AC 215 ms
85,384 KB
testcase_30 AC 205 ms
85,188 KB
testcase_31 AC 1 ms
4,380 KB
testcase_32 AC 280 ms
124,304 KB
testcase_33 AC 286 ms
124,332 KB
testcase_34 AC 187 ms
95,132 KB
testcase_35 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <assert.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#define REP(i, n) for (int i = 0; i < n; i++)
#define RREP(i, n) for (int i = n - 1; i >= 0; i--)
#define FOR(i, a, b) for (int i = a; i <= b; i++)
#define RFOR(i, a, b) for (int i = a; i >= b; i--)

const int mod = 1000000007;

typedef struct {
    long long a, b, c;
    bool has_only_a;
} expr_t;

const expr_t expr_unit = { 1, .has_only_a = true };

expr_t *expr_concat(const expr_t *l, const expr_t *r) {
    expr_t *const expr = malloc(sizeof(expr_t));
    if (l->has_only_a && r->has_only_a) {
        expr->a = l->a * r->a % mod;
        expr->has_only_a = true;
    }
    else if (l->has_only_a && !r->has_only_a) {
        expr->a = l->a * r->a % mod;
        expr->b = r->b;
        expr->c = r->c;
        expr->has_only_a = false;
    }
    else if (!l->has_only_a && r->has_only_a) {
        expr->a = l->a;
        expr->b = l->b;
        expr->c = l->c * r->a % mod;
        expr->has_only_a = false;
    }
    else if (!l->has_only_a && !r->has_only_a) {
        expr->a = l->a;
        expr->b = (l->b + l->c * r->a + r->b) % mod;
        expr->c = r->c;
        expr->has_only_a = false;
    }
    else assert(false);
    return expr;
}
expr_t *expr_create(const char *c, int i) {
    expr_t *const expr = malloc(sizeof(expr_t));
    const int r = c[i] - '0';
    if (i == 0 || c[i - 1] == '+') {
        expr->a = 1;
        expr->b = 0;
        expr->c = r;
        expr->has_only_a = false;
    }
    else {
        expr->a = r;
        expr->has_only_a = true;
    }
    return expr;
}

typedef struct {
    const expr_t **tree;
    int size;
} segtree_t;

segtree_t *segtree_create(const char *c, int n) {
    segtree_t *const st = malloc(sizeof(segtree_t));
    st->size = 1;
    while (st->size < n) st->size <<= 1;
    st->tree = malloc(sizeof(expr_t) * (st->size << 1));
    REP(i, st->size)
        st->tree[i + st->size] = i < n
            ? expr_create(c, (i + 1) << 1)
            : &expr_unit;
    RFOR(i, st->size - 1, 1)
        st->tree[i] = expr_concat(st->tree[i << 1], st->tree[(i << 1) + 1]);
    return st;
}

void segtree_update(const segtree_t *st, int i, const expr_t *expr) {
    st->tree[i += st->size] = expr;
    for (i >>= 1; i > 0; i >>= 1)
        st->tree[i] = expr_concat(st->tree[i << 1], st->tree[(i << 1) + 1]);
}

expr_t *segtree_append(const segtree_t *st, int l, int r) {
    const expr_t *lacc = &expr_unit;
    const expr_t *racc = &expr_unit;
    for (l += st->size, r += st->size + 1; l < r; l >>= 1, r >>= 1) {
        if (l & 1) lacc = expr_concat(lacc, st->tree[l++]);
        if (r & 1) racc = expr_concat(st->tree[--r], racc);
    }
    return expr_concat(lacc, racc);
}

int main() {
    int n;
    scanf("%d", &n);
    char c[n];
    REP(i, n) scanf("%*c%c", &c[i]);
    const segtree_t *const segtree = segtree_create(c, n >> 1);
    int q;
    scanf("%d", &q);
    REP(i, q) {
        char t;
        int x, y;
        scanf("%*c%c %d %d", &t, &x, &y);
        if (t == '!') {
            x--; y--;
            char tmp = c[x];
            c[x] = c[y];
            c[y] = tmp;
            segtree_update(segtree, (x - 1) >> 1, expr_create(c, x + (x & 1)));
            segtree_update(segtree, (y - 1) >> 1, expr_create(c, y + (y & 1)));
        }
        else {
            x--; y--;
            const expr_t *const expr = segtree_append(segtree, x >> 1, (y >> 1) - 1);
            printf("%lld\n", ((c[x] - '0') * expr->a + expr->b + expr->c) % mod);
        }
    }
    return 0;
}
0