QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525832 | #8061. Add or Multiply | quannnguyen2009 | WA | 398ms | 25052kb | C++14 | 4.6kb | 2024-08-20 23:17:30 | 2024-08-20 23:17:30 |
Judging History
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';
else 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: 7808kb
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: 0ms
memory: 5612kb
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: 132ms
memory: 25052kb
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: 273ms
memory: 24996kb
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: 398ms
memory: 24904kb
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 89867th lines differ - expected: '809467070', found: '860060668'