제출 #651003

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
651003		bebra	Automobil (COCI17_automobil)	C++17	100 / 100	99 ms	39500 KiB

automobil

#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 / 100