結果

問題 No.619 CardShuffle
ユーザー くれちー
提出日時 2017-12-11 18:32:51
言語 C
(gcc 13.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 34 WA * 1
権限があれば一括ダウンロードができます

ソースコード

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