oj.uz

Submission #651003

# Submission time Handle Problem Language Result Execution time Memory
651003 2022-10-16T10:41:39 Z bebra Automobil (COCI17_automobil) C++17
100 / 100
 99 ms 39500 KB 
#define _GLIBCXX_DEBUG_PEDANTIC
#include <bits/stdc++.h>
#define int long long
using namespace std;
using ll = long long;

#define dbg(x) cerr << #x << ": " << x << endl;

const ll MOD = 1e9 + 7;
const ll INV2 = 500000004;

const int MAX_N = 1e6 + 5;
ll cols[MAX_N];
ll rows[MAX_N];
ll v[MAX_N];

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n, m;
    cin >> n >> m;
    int k;
    cin >> k;
    ll cnt = n * m % MOD;
    ll sum = cnt * (cnt + 1) % MOD * INV2 % MOD;
    for (ll pos = 1; pos <= n; ++pos) {
        ll row_sum = m * ((1 + (pos - 1) * m % MOD) * 2 + m - 1) % MOD * INV2 % MOD;
        rows[pos] = row_sum;
        v[pos] = 1;
    }
    for (ll pos = 1; pos <= m; ++pos) {
        ll column_sum = n * (pos * 2 % MOD + (n - 1) * m % MOD) % MOD * INV2 % MOD;
        cols[pos] = column_sum;
    }
    vector<pair<int, ll>> rows_changes, cols_changes;
    unordered_set<int> col, row;
    for (int t = 0; t < k; ++t) {
        char type;
        cin >> type;
        int pos;
        cin >> pos;
        ll value;
        cin >> value;
        if (type == 'R') {
            rows_changes.emplace_back(pos, value);
            row.insert(pos);
            v[pos] = v[pos] * value % MOD;
        } else {
            cols_changes.emplace_back(pos, value);
            col.insert(pos);
        }
    }
    for (const auto& [pos, value] : rows_changes) {
        sum = (sum - rows[pos]) % MOD;
        rows[pos] = rows[pos] * value % MOD;
        sum = (sum + rows[pos]) % MOD;
        if (sum < 0) sum += MOD;
    }
    map<pair<int, int>, ll> used_cells;
    for (const auto& i : row) {
        ll value_i = v[i];
        for (const auto& j : col) {
            ll prev_value;
            if (used_cells.find({i, j}) != used_cells.end()) {
                prev_value = used_cells[{i, j}];
            } else {
                prev_value = (i - 1) * m + j;
                prev_value %= MOD;
            }
            cols[j] = (cols[j] - prev_value) % MOD;
            prev_value = prev_value * value_i % MOD;

            used_cells[{i, j}] = prev_value;
            cols[j] = (cols[j] + prev_value) % MOD;
            if (cols[j] < 0) cols[j] += MOD;
             
        }
    }
    for (const auto& [pos, value] : cols_changes) {
        sum = (sum - cols[pos]) % MOD;
        cols[pos] = cols[pos] * value % MOD;
        sum = (sum + cols[pos]) % MOD;
        if (sum < 0) sum += MOD;
    }
    cout << sum << '\n';
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 724 KB Output is correct
2 Correct 17 ms 3720 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 6 ms 1492 KB Output is correct
5 Correct 13 ms 3204 KB Output is correct
6 Correct 4 ms 1364 KB Output is correct
7 Correct 23 ms 5324 KB Output is correct
8 Correct 6 ms 1876 KB Output is correct
9 Correct 17 ms 4308 KB Output is correct
10 Correct 26 ms 6144 KB Output is correct
11 Correct 24 ms 9076 KB Output is correct
12 Correct 76 ms 28672 KB Output is correct
13 Correct 15 ms 4308 KB Output is correct
14 Correct 14 ms 16852 KB Output is correct
15 Correct 60 ms 23888 KB Output is correct
16 Correct 96 ms 39452 KB Output is correct
17 Correct 90 ms 39500 KB Output is correct
18 Correct 91 ms 39440 KB Output is correct
19 Correct 96 ms 39476 KB Output is correct
20 Correct 99 ms 39368 KB Output is correct