제출 #1097067

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1097067		vjudge1	Automobil (COCI17_automobil)	C++17	55 / 100	1078 ms	8284 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;
}
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 = fi + (len - 1) * d;
        return mul(mul(add(fi, last), len), 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;
    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> rowGreaterThan1;
    int res = 0;
    for (int i = 1 ; i <= n; ++i)
    {
        if (hRow[i] != 1)
        {
            rowGreaterThan1.push_back(i);
            for (int j = 1; j <= m; ++j)
                res = add(res, mul(hRow[i], mul(hCol[j], (i - 1) * m + j)));
        }
    }
    assert(rowGreaterThan1.size() <= 1000);
    for (int j = 1; j <= m; ++j)
    {
        res = add(res, mul(hCol[j], sum_progress(j, n, m)));
        for (auto i: rowGreaterThan1)
            res = sub(res, mul(hCol[j], (i - 1) * m + j));
    }
    cout << res;
}

• Subtask 1: 55 / 100