QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#726817 | #8061. Add or Multiply | Broder | WA | 0ms | 3508kb | C++17 | 5.2kb | 2024-11-09 09:03:40 | 2024-11-09 09:03:41 |
Judging History
answer
#include <bits/stdc++.h>
#include <iostream>
#include <vector>
#include <string>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
struct Node {
int l, r;
ll value;
bool is_term;
Node *left, *right;
Node() : l(0), r(0), value(0), is_term(true), left(nullptr), right(nullptr) {}
};
vector<int> numbers; // Numbers in the expression
vector<int> operators; // Operators in the original expression (0: '+', 1: '*')
vector<int> operators_flip; // Operators in the flipped expression
int N, M;
bool operators_flipped = false; // Flag indicating if 'a' operation has been performed
void build(Node* node, int l, int r, vector<int>& ops) {
node->l = l;
node->r = r;
if (l == r) {
node->value = numbers[l];
node->is_term = true;
node->left = node->right = nullptr;
} else {
int mid = (l + r) / 2;
node->left = new Node();
node->right = new Node();
build(node->left, l, mid, ops);
build(node->right, mid + 1, r, ops);
int op = ops[mid]; // Operator between positions mid and mid+1
if (node->left->is_term && node->right->is_term && op == 1) { // '*'
node->value = (node->left->value * node->right->value) % MOD;
node->is_term = true;
} else {
node->value = (node->left->value + node->right->value) % MOD;
node->is_term = false;
}
}
}
void update_number(Node* node, int pos, int new_value, vector<int>& ops) {
if (node->l == node->r) {
if (node->l == pos) {
node->value = new_value;
// node->is_term remains true
}
} else {
if (pos <= node->left->r) {
update_number(node->left, pos, new_value, ops);
} else {
update_number(node->right, pos, new_value, ops);
}
int mid = node->left->r;
int op = ops[mid]; // Operator between mid and mid+1
if (node->left->is_term && node->right->is_term && op == 1) { // '*'
node->value = (node->left->value * node->right->value) % MOD;
node->is_term = true;
} else {
node->value = (node->left->value + node->right->value) % MOD;
node->is_term = false;
}
}
}
void update_operator(Node* node, int pos, vector<int>& ops) {
if (node->r < pos || node->l > pos + 1) {
// The operator does not affect this node
return;
}
if (node->l == node->r) {
// Leaf node, no operators to update
return;
} else {
update_operator(node->left, pos, ops);
update_operator(node->right, pos, ops);
int mid = node->left->r;
int op = ops[mid]; // Operator between mid and mid+1
if (node->left->is_term && node->right->is_term && op == 1) { // '*'
node->value = (node->left->value * node->right->value) % MOD;
node->is_term = true;
} else {
node->value = (node->left->value + node->right->value) % MOD;
node->is_term = false;
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> N >> M;
string expr;
cin >> expr;
numbers.resize(N + 1);
operators.resize(N); // operators[1..N-1]
operators_flip.resize(N);
int idx = 1; // Position in numbers
for (int i = 0; i < expr.size(); ) {
if (isdigit(expr[i])) {
numbers[idx] = expr[i] - '0';
idx++;
i++;
} else {
int op = (expr[i] == '+') ? 0 : 1;
operators[idx - 1] = op;
operators_flip[idx - 1] = 1 - op;
i++;
}
}
Node* root_normal = new Node();
build(root_normal, 1, N, operators);
Node* root_flipped = new Node();
build(root_flipped, 1, N, operators_flip);
// Output initial value
cout << root_normal->value << '\n';
for (int q = 0; q < M; q++) {
string command;
cin >> command;
if (command == "s") {
int i, j;
cin >> i >> j;
swap(numbers[i], numbers[j]);
// Update both trees
update_number(root_normal, i, numbers[i], operators);
update_number(root_normal, j, numbers[j], operators);
update_number(root_flipped, i, numbers[i], operators_flip);
update_number(root_flipped, j, numbers[j], operators_flip);
} else if (command == "f") {
int i;
cin >> i;
// Flip operator at position i
operators[i] = 1 - operators[i];
operators_flip[i] = 1 - operators_flip[i];
// Update both trees
update_operator(root_normal, i, operators);
update_operator(root_flipped, i, operators_flip);
} else if (command == "a") {
// Flip the operators flag
operators_flipped = !operators_flipped;
}
// Output current value
if (!operators_flipped) {
cout << root_normal->value << '\n';
} else {
cout << root_flipped->value << '\n';
}
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3508kb
input:
3 4 2+3*4 s 1 2 a f 2 a
output:
9 9 10 24 9
result:
wrong answer 1st lines differ - expected: '14', found: '9'