QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#525470 | #8061. Add or Multiply | quannnguyen2009 | WA | 1ms | 7812kb | C++14 | 4.5kb | 2024-08-20 16:52:09 | 2024-08-20 16:52:09 |
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);
}
cout << ans[t] << '\n';
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 7812kb
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: 1ms
memory: 5692kb
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 61 62 750000008
result:
wrong answer 10th lines differ - expected: '74', found: '61'