#222827 (C) No.619 CardShuffle

• 問題: No.619 CardShuffle
• ユーザー: くれちー
• 提出日時: 2017-12-11 18:32:51
• 言語: C (gcc 12.3.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 3,536 bytes
• コンパイル時間: 740 ms
• コンパイル使用メモリ: 32,384 KB
• 実行使用メモリ: 163,456 KB
• 最終ジャッジ日時: 2024-12-22 21:03:36
• 合計ジャッジ時間: 7,763 ms
• ジャッジサーバーID （参考情報）: judge2 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	1 ms; 5,248 KB
testcase_01	AC	1 ms; 5,248 KB
testcase_02	AC	1 ms; 5,248 KB
testcase_03	AC	1 ms; 5,248 KB
testcase_04	AC	1 ms; 5,248 KB
testcase_05	AC	1 ms; 5,248 KB
testcase_06	AC	1 ms; 5,248 KB
testcase_07	AC	1 ms; 5,248 KB
testcase_08	AC	1 ms; 5,248 KB
testcase_09	AC	1 ms; 5,248 KB
testcase_10	AC	2 ms; 5,248 KB
testcase_11	AC	1 ms; 5,248 KB
testcase_12	AC	1 ms; 5,248 KB
testcase_13	AC	1 ms; 5,248 KB
testcase_14	AC	1 ms; 5,248 KB
testcase_15	AC	2 ms; 5,248 KB
testcase_16	AC	319 ms; 124,672 KB
testcase_17	AC	313 ms; 124,416 KB
testcase_18	AC	353 ms; 124,288 KB
testcase_19	AC	304 ms; 124,032 KB
testcase_20	AC	300 ms; 124,160 KB
testcase_21	AC	392 ms; 163,456 KB
testcase_22	AC	367 ms; 163,328 KB
testcase_23	AC	377 ms; 163,456 KB
testcase_24	AC	361 ms; 163,200 KB
testcase_25	AC	358 ms; 163,200 KB
testcase_26	AC	225 ms; 85,248 KB
testcase_27	AC	217 ms; 85,248 KB
testcase_28	AC	221 ms; 85,248 KB
testcase_29	AC	217 ms; 85,376 KB
testcase_30	AC	210 ms; 85,248 KB
testcase_31	AC	1 ms; 5,248 KB
testcase_32	AC	292 ms; 124,288 KB
testcase_33	AC	306 ms; 124,288 KB
testcase_34	AC	190 ms; 95,104 KB
testcase_35	WA	-

ソースコード

#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;
}