QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726707 | #8061. Add or Multiply | Tenshi# | WA | 0ms | 3780kb | C++17 | 4.5kb | 2024-11-09 06:04:42 | 2024-11-09 06:04:43 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
using pii=pair<long long, int>;
#define rep(i, n) for (int i = 0; i < n; i++)
#define sz(x) (long long)(x).size()
typedef long long ll;
#define int ll
vector<ll> vals;
vector<char> ops;
ll MOD = 1e9+7;
ll op(ll a, char o, ll b) {
if (o == '+') {
return (a+b)%MOD;
}
else if (o=='*'){
return (a*b)%MOD;
}
else {
assert(1==0);
return -1;
}
}
struct segTreeNode {
int lo, md, hi;
ll a = 0, b = 0, c = 0;
segTreeNode *left, *right;
bool singular = false;
char o = 'a';
segTreeNode(int L, int R) {
lo = L, hi = R;
md = (lo + hi)/2;
if (lo == hi) {
singular = true;
b = vals[lo]%MOD;
return;
}
o = ops[md];
left = new segTreeNode(L, md);
right = new segTreeNode(md+1, R);
merge();
}
void merge() {
if (left->singular and right->singular) {
if (o=='*') {
singular = true;
a = 0;
b = (left->b * right->b)%MOD;
c = 0;
}
else {
a = left->b;
b = 0;
c = right->b;
}
return;
}
if (left->singular) {
if (o == '+') {
a = left->b;
b = (right->a+right->b)%MOD;
c = right->c;
}
else {
a = op(right->a, o, left->b)%MOD;
b = right->b;
c = right->c;
}
return;
}
if (right->singular) {
if (o == '+') {
a = left->a;
b = (left->b+left->c)%MOD;
c = right->b;
}
else {
a = left->a;
b = left->b;
c = op(left->c, o, right->b)%MOD;
}
return;
}
a = left->a;
b = (left->b + op(left->c, o, right->a) + right->b)%MOD;
c = right->c;
}
void update(int idx) {
if (md == idx) {
if (o=='+') {
o = '*';
}
else {
o = '+';
}
}
else if (idx < md) {
left->update(idx);
}
else {
right->update(idx);
}
merge();
}
void updateval(int idx) {
// cout << lo << ' ' << hi << endl;
if (lo==hi) {
assert(lo == idx);
a = 0;
b = vals[idx];
c = 0;
singular = true;
return;
}
else if (idx <= md) {
left->updateval(idx);
}
else {
right->updateval(idx);
}
merge();
}
};
signed main(){
int n, m; cin>>n>>m;
string s; cin >> s;
vals = vector<ll>(n);
rep (i, n) {
vals[i] = s[2*i]-'0';
}
ops = vector<char>(n-1);
rep (i, n-1) {
ops[i] = s[i*2+1];
}
rep(i, n-1) {
if (ops[i]=='+') {
ops[i] = '*';
}
else {
ops[i] = '+';
}
}
segTreeNode* evilst = new segTreeNode(0, n-1);
rep(i, n-1) {
if (ops[i]=='+') {
ops[i] = '*';
}
else {
ops[i] = '+';
}
}
segTreeNode* st = new segTreeNode(0, n-1);
bool evil = false;
cout << (st->a + st->b + st->c)%MOD << endl;
rep(i, m) {
char d; cin >> d;
if (d=='s') {
int a, b; cin >> a >> b;
a--;
b--;
swap(vals[a], vals[b]);
st->updateval(a);
st->updateval(b);
evilst->updateval(a);
evilst->updateval(b);
}
else if (d=='a') {
evil = !evil;
}
else {
int a; cin >> a;
evilst->update(a-1);
st->update(a-1);
}
if (evil) {
// cout << evilst->right->a << ' ' << evilst->right->b << ' ' << evilst->right->c << endl;
cout << (evilst->a + evilst->b + evilst->c)%MOD << endl;
}
else {
// cout << st->right->a << ' ' << st->right->b << ' ' << st->right->c << endl;
cout << (st->a + st->b + st->c)%MOD << endl;
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3780kb
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: 0ms
memory: 3476kb
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 6 91 51 56 999999965
result:
wrong answer 8th lines differ - expected: '125000014', found: '6'