QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#726817#8061. Add or MultiplyBroderWA 0ms3508kbC++175.2kb2024-11-09 09:03:402024-11-09 09:03:41

Judging History

你现在查看的是最新测评结果

  • [2024-11-09 09:03:41]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3508kb
  • [2024-11-09 09:03:40]
  • 提交

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'