Submission #1097096

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097096		vjudge1	Automobil (COCI17_automobil)	C++17	100 / 100	13 ms	16148 KiB

automobil

#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define debug(x) cerr << #x << " = " << x << endl
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define __builtin_popcount __builtin_popcountll
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
template <class T, class T2> ostream &operator<<(ostream &o, pair<T, T2> p)
{
    o << "(" << p.first << ", " << p.second << ")"; 
    return o;
}
#define int long long
namespace ModInt
{
    const int MOD = 1e9 + 7;
    int add(int x, int y)
    {
        return (x + y) % MOD;
    }
    int sub(int x, int y)
    {
        return (x - y + MOD) % MOD;
    }
    int mul(int x, int y)
    {
        return 1ll * x * y % MOD;
    }
    int pow_mod(int x, int y)
    {
        if (y == 0)
            return 1;
        int t = pow_mod(x, y >> 1);
        if (y % 2 == 0)
            return mul(t, t);
        return mul(x, mul(t, t));
    }
    const int INV2 = pow_mod(2, MOD - 2);
    int sum_progress(int fi, int len, int d)
    {
        int last = add(fi, mul(sub(len, 1), d));
        return mul(mul(add(fi, last), len % MOD), INV2);  
    }
}

using namespace ModInt;
signed main()
{
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    auto get_val = [&](int row, int y)
    {
        return add(mul(row - 1, m), y);
    };
    vector <int> hRow(n + 1, 1), hCol(m + 1, 1);
    while (q--)
    {
        char type;
        int pos, val;
        cin >> type >> pos >> val;
        if (type == 'R')
            hRow[pos] = mul(hRow[pos], val);
        else
            hCol[pos] = mul(hCol[pos], val);
    }
    vector <int> rowDiff1, colDiff1;
    for (int i = 1 ; i <= n; ++i)
    {
        if (hRow[i] != 1)
            rowDiff1.push_back(i);
    }
    for (int j = 1; j <= m; ++j)
    {
        if (hCol[j] != 1)
            colDiff1.push_back(j);
    }
    int res = sum_progress(1, n * m, 1);
    for (auto row: rowDiff1)
    {
        int tmp = sum_progress(get_val(row, 1), m, 1);
        res = sub(res, tmp);
        res = add(res, mul(hRow[row], tmp));
    }
    for (auto col: colDiff1)
    {
        int tmp = sum_progress(get_val(1, col), n, m);
        res = sub(res, tmp);
        res = add(res, mul(hCol[col], tmp));
    }
    for (auto row: rowDiff1)
    {
        for (auto col: colDiff1)
        {
            res = sub(res, mul(sub(add(hRow[row], hCol[col]), 1), get_val(row, col)));
            res = add(res, mul(mul(hRow[row], hCol[col]), get_val(row, col)));
        }
    }
    cout << res;
    cerr << TIME;
}

• Subtask 1: 100 / 100