QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525478 | #8061. Add or Multiply | quannnguyen2009 | WA | 319ms | 25016kb | C++14 | 4.5kb | 2024-08-20 16:56:29 | 2024-08-20 16:56:29 |
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];
}
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'