QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#726707#8061. Add or MultiplyTenshi#WA 0ms3780kbC++174.5kb2024-11-09 06:04:422024-11-09 06:04:43

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 06:04:43]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3780kb
  • [2024-11-09 06:04:42]
  • 提交

answer

#include<bits/stdc++.h>

using namespace std;

using pii=pair<long long, int>;

#define rep(i, n) for (int i = 0; i < n; i++)
#define sz(x) (long long)(x).size()

typedef long long ll;
#define int ll
vector<ll> vals;
vector<char> ops;

ll MOD = 1e9+7;

ll op(ll a, char o, ll b) {
    if (o == '+') {
        return (a+b)%MOD;
    }
    else if (o=='*'){
        return (a*b)%MOD;
    }
    else {
        assert(1==0);
        return -1;
    }
}



struct segTreeNode {
    int lo, md, hi;
    ll a = 0, b = 0, c = 0;

    segTreeNode *left, *right;
    bool singular = false;
    char o = 'a';
    segTreeNode(int L, int R) {
        lo = L, hi = R;
        md = (lo + hi)/2;
        if (lo == hi) {
            singular = true;
            b = vals[lo]%MOD;
            return;
        }
        o = ops[md];
        left = new segTreeNode(L, md);
        right = new segTreeNode(md+1, R);
        merge();
    }

    void merge() {
        if (left->singular and right->singular) {
            if (o=='*') {
                singular = true;
                a = 0;
                b = (left->b * right->b)%MOD;
                c = 0;
            }
            else {
                a = left->b;
                b = 0;
                c = right->b;
            }
            return;
        }
        if (left->singular) {
            if (o == '+') {
                a = left->b;
                b = (right->a+right->b)%MOD;
                c = right->c;
            }
            else {
                a = op(right->a, o, left->b)%MOD;
                b = right->b;
                c = right->c;
            }
            return;
        }
        if (right->singular) {
            if (o == '+') {
                a = left->a;
                b = (left->b+left->c)%MOD;
                c = right->b;
            }
            else {
                a = left->a;
                b = left->b;
                c = op(left->c, o, right->b)%MOD;
            }
            return;
        }
        a = left->a;
        b = (left->b + op(left->c, o, right->a) + right->b)%MOD;
        c = right->c;
    }

    void update(int idx) {
        if (md == idx) {
            if (o=='+') {
                o = '*';
            }
            else {
                o = '+';
            }
        }
        else if (idx < md) {
            left->update(idx);
        }
        else {
            right->update(idx);
        }
        merge();
    }

    void updateval(int idx) {
        // cout << lo << ' ' << hi << endl;
        if (lo==hi) {
            assert(lo == idx);
            a = 0;
            b = vals[idx];
            c = 0;
            singular = true;
            return;
        }
        else if (idx <= md) {
            left->updateval(idx);
        }
        else {
            right->updateval(idx);
        }
        merge();
    }
};

signed main(){
    int n, m; cin>>n>>m;
    string s; cin >> s;
    vals = vector<ll>(n);
    rep (i, n) {
        vals[i] = s[2*i]-'0';
    }
    ops = vector<char>(n-1);
    rep (i, n-1) {
        ops[i] = s[i*2+1];
    }
    rep(i, n-1) {
        if (ops[i]=='+') {
            ops[i] = '*';
        }
        else {
            ops[i] = '+';
        }
    }
    segTreeNode* evilst = new segTreeNode(0, n-1);
    rep(i, n-1) {
        if (ops[i]=='+') {
            ops[i] = '*';
        }
        else {
            ops[i] = '+';
        }
    }
    segTreeNode* st = new segTreeNode(0, n-1);
    bool evil = false;
    cout << (st->a + st->b + st->c)%MOD << endl;
    rep(i, m) {
        char d; cin >> d;
        if (d=='s') {
            int a, b; cin >> a >> b;
            a--;
            b--;
            swap(vals[a], vals[b]);
            st->updateval(a);
            st->updateval(b);
            evilst->updateval(a);
            evilst->updateval(b);
        }
        else if (d=='a') { 
            evil = !evil;
        }
        else { 
            int a; cin >> a;
            evilst->update(a-1);
            st->update(a-1);
        }
        if (evil) { 
            
            // cout << evilst->right->a << ' ' <<  evilst->right->b << ' ' <<  evilst->right->c << endl;
            cout << (evilst->a +  evilst->b +  evilst->c)%MOD << endl;

        }
        else {
            // cout << st->right->a << ' ' <<  st->right->b << ' ' <<  st->right->c << endl;
            cout << (st->a +  st->b +  st->c)%MOD << endl;
        }
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3780kb

input:

3 4
2+3*4
s 1 2
a
f 2
a

output:

14
11
10
24
9

result:

ok 5 lines

Test #2:

score: -100
Wrong Answer
time: 0ms
memory: 3476kb

input:

15 11
8*5*5*5*8*5*5*5*8*5*5*5+1+2+3
f 14
s 15 15
s 1 1
s 15 1
s 1 15
f 13
f 1
a
f 1
f 12
a

output:

1000000006
0
0
0
375000017
0
1000000006
6
91
51
56
999999965

result:

wrong answer 8th lines differ - expected: '125000014', found: '6'