QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525478#8061. Add or Multiplyquannnguyen2009WA 319ms25016kbC++144.5kb2024-08-20 16:56:292024-08-20 16:56:29

Judging History

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

  • [2024-08-20 16:56:29]
  • 评测
  • 测评结果:WA
  • 用时:319ms
  • 内存:25016kb
  • [2024-08-20 16:56:29]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N=2e5+5, mod = 1e9+7, inf = 1e18;

int n, q;
int a[N];
int op[N]; // luu op o vi tri i
int g[N][2]; //luu gia tri cac khoang
set<int> st[2]; //luu idx cac khoang
int ans[2];
vector<int> seg;

int binpow(int a, int b) {
    int ans = 1;
    while(b>0) {
        if(b&1) ans = (ans*a)%mod;
        a = (a*a)%mod;
        b>>=1;
    }
    return ans;
}

void bld(int node, int l, int r) {
    if(l==r) {
        seg[node] = a[l];
        return;
    }
    int mid = (l+r)>>1;
    bld(node<<1, l, mid); bld(node<<1|1, mid+1, r);
    seg[node] = (seg[node<<1]*seg[node<<1|1])%mod;
}

void upd(int node, int l, int r, int idx, int val) {
    if(l>idx || r<idx) return;
    if(l==r) {
        seg[node] = val;
        return;
    }
    int mid = (l+r)>>1;
    upd(node<<1, l, mid, idx, val); upd(node<<1|1, mid+1, r, idx, val);
    seg[node] = (seg[node<<1]*seg[node<<1|1])%mod;
}

int get(int node, int l, int r, int ql, int qr) {
    if(ql>r || qr<l) return 1;
    if(ql<=l && r<=qr) return seg[node];
    int mid = (l+r)>>1;
    return (get(node<<1, l, mid, ql, qr)*get(node<<1|1, mid+1, r, ql, qr))%mod;
}


signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    char c;
    for (int i=1; i<2*n; i++) {
        cin >> c;
        if(i%2==1) {
            a[i/2+1] = (c-'0');
        } else {
            if(c=='+') op[i/2+1]=0;
            else op[i/2+1]=1;
        }
    }
    seg.resize(4*n+5);
    bld(1, 1, n);

    for (int i=1; i<=n; i++) {
        int idx = i;
        int res = a[idx];
        while(idx<n && op[idx+1]) {
            idx++; res = (res*a[idx])%mod;
        }
        g[i][0] = res;
        st[0].insert(i);
        ans[0] = (ans[0]+res)%mod;
        i = idx;
    }
    for (int i=1; i<=n; i++) {
        int idx = i;
        int res = a[idx];
        while(idx<n && !op[idx+1]) {
            idx++; res = (res*a[idx])%mod;
        }
        g[i][1] = res;
        st[1].insert(i);
        ans[1] = (ans[1]+res)%mod;
        i = idx;
    }

    int t = 0;
    cout << ans[t] << '\n';
    while(q--) {
        char type; cin >> type;
        if(type=='a') {
            t = 1-t;
        } else if(type=='s') {
            int x, y; cin >> x >> y;
            int gx = *prev(st[0].upper_bound(x)), gy = *prev(st[0].upper_bound(y));
            int vx = binpow(a[x], mod-2), vy = binpow(a[y], mod-2);
            ans[0] = (ans[0]-g[gx][0]+mod)%mod; ans[0] = (ans[0]-g[gy][0]+mod)%mod;
            g[gx][0] = (g[gx][0]*vx)%mod; g[gx][0] = (g[gx][0]*a[y]);
            g[gy][0] = (g[gy][0]*vy)%mod; g[gy][0] = (g[gy][0]*a[x]);
            ans[0] = (ans[0]+g[gx][0])%mod; ans[0] = (ans[0]+g[gy][0])%mod;

            gx = *prev(st[1].upper_bound(x)), gy = *prev(st[1].upper_bound(y));
            ans[1] = (ans[1]-g[gx][1]+mod)%mod; ans[1] = (ans[1]-g[gy][1]+mod)%mod;
            g[gx][1] = (g[gx][1]*vx)%mod; g[gx][1] = (g[gx][1]*a[y]);
            g[gy][1] = (g[gy][1]*vy)%mod; g[gy][1] = (g[gy][1]*a[x]);
            ans[1] = (ans[1]+g[gx][1])%mod; ans[1] = (ans[1]+g[gy][1])%mod;
            upd(1, 1, n, x, a[y]); upd(1, 1, n, y, a[x]);
            swap(a[x], a[y]);
        }  else {
            int idx; cin >> idx; idx++;
            int gn = idx, gp = *prev(st[op[idx]].upper_bound(idx-1));
            ans[op[idx]] = (ans[op[idx]]-g[gp][op[idx]]+mod)%mod; ans[op[idx]] = (ans[op[idx]]-g[gn][op[idx]]+mod)%mod;
            g[gp][op[idx]] = (g[gp][op[idx]]*g[gn][op[idx]])%mod; g[gn][op[idx]] = 0;
            ans[op[idx]] = (ans[op[idx]]+g[gp][op[idx]])%mod;
            st[op[idx]].erase(gn);

            gp = *prev(st[!op[idx]].upper_bound(idx));
            int en;
            if(st[!op[idx]].upper_bound(idx)==st[!op[idx]].end()) en=n+1;
            else en = *st[!op[idx]].upper_bound(idx);
            ans[!op[idx]] = (ans[!op[idx]]-g[gp][!op[idx]]+mod)%mod; ans[!op[idx]] = (ans[!op[idx]]-g[idx][!op[idx]]+mod)%mod;
            g[gp][!op[idx]] = get(1, 1, n, gp, idx-1); g[idx][!op[idx]] = get(1, 1, n, idx, en-1);
            ans[!op[idx]] = (ans[!op[idx]]+g[gp][!op[idx]])%mod; ans[!op[idx]] = (ans[!op[idx]]+g[idx][!op[idx]])%mod;
            st[!op[idx]].insert(idx);
            op[idx] = !op[idx];
        }
        cout << ans[t] << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5608kb

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: 0
Accepted
time: 1ms
memory: 5696kb

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
125000014
101
74
75
999999965

result:

ok 12 lines

Test #3:

score: 0
Accepted
time: 153ms
memory: 25016kb

input:

200000 200000
3*5*6*3*7*3*4*7*2*9*2*7*5*9*2*9*5*4*6*3*7*2*8*6*6*8*4*2*4*5*5*8*9*4*9*2*7*5*4*3*9*4*8*5*5*6*5*3*8*5*9*2*7*8*8*6*7*6*6*5*7*8*3*7*3*5*9*3*7*5*6*8*2*5*6*5*2*9*7*8*7*4*9*3*9*5*4*5*4*3*4*4*9*6*4*5*4*8*9*8*5*9*9*9*8*6*9*6*5*8*5*5*6*9*2*6*9*6*5*4*7*6*5*4*8*3*5*8*5*5*5*7*4*2*4*8*2*5*6*3*9*7*5*...

output:

454019263
484673093
1099983
1099976
454019263
779145621
1099999
1099976
454019263
922488446
1099979
1099976
454019263
125627827
1100003
1099976
454019263
457373538
1100005
1099976
454019263
49928396
1100017
1099976
454019263
361222530
1099999
1099976
454019263
267241834
1099993
1099976
454019263
911...

result:

ok 200001 lines

Test #4:

score: -100
Wrong Answer
time: 319ms
memory: 24984kb

input:

200000 200000
7*5*4+7+2*5*3*3+2*7*3+2+6+8+9*7+3*3+7+3*4*6*4+8+9*5*9*3+3+1+4+6+6+1*2+3*6+9*8*1*6*7*9+2*2+6+3+3*9*3+8*2+7+8+4*3+6+3+9*7*7+2*4*4*9*6*3*1+7+9*2*2+1+8*7+5+8+5+4+1*2+4*8+6+5*7+5+1+3+5+7+3+9+6+1+8+4+9+5+2+4*7*1*3*6*3+8+1*6*9*1+8+6+5+1*8*2*1*5*9+8+7+4+3+9+8*4*9*3*8*1*2*2*2+4+5+6*8*9+8*9+1*9*...

output:

408005284
408005259
631073017
631073018
408005259
408005259
408003705
408003734
408003695
407908446
407907522
407907744
407907928
407907041
407906852
631911412
631911441
631911418
408254984
408254607
408254489
408254471
408254478
408254478
408254498
408254498
408253239
623746881
623746889
623752256
...

result:

wrong answer 15104th lines differ - expected: '269114462', found: '-730885545'