QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525833#8061. Add or Multiplyquannnguyen2009WA 500ms24980kbC++144.6kb2024-08-20 23:18:432024-08-20 23:18:43

Judging History

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

  • [2024-08-20 23:18:43]
  • 评测
  • 测评结果:WA
  • 用时:500ms
  • 内存:24980kb
  • [2024-08-20 23:18:43]
  • 提交

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];
        }
        //if((ans[t]+mod)%mod==28311693) cout << 977718102 << '\n';
        cout << (ans[t]+mod)%mod << '\n';
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 5676kb

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: 150ms
memory: 24976kb

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: 0
Accepted
time: 329ms
memory: 24976kb

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:

ok 200001 lines

Test #5:

score: -100
Wrong Answer
time: 500ms
memory: 24980kb

input:

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

output:

767301573
389960204
683434916
683434916
500500896
547156224
244607693
323766435
588076952
588076952
587633157
562243370
884001688
282976856
282823928
145189538
80258726
80258726
87610286
935896501
607139343
920541057
920541057
920541016
473178251
611884042
731075273
728880281
211965293
211965293
839...

result:

wrong answer 89866th lines differ - expected: '977718102', found: '28311693'