oj.uz

Submission #1097096

# Submission time Handle Problem Language Result Execution time Memory
1097096 2024-10-06T03:55:00 Z vjudge1 Automobil (COCI17_automobil) C++17
100 / 100
 13 ms 16148 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 2908 KB Output is correct
12 Correct 7 ms 8796 KB Output is correct
13 Correct 1 ms 1068 KB Output is correct
14 Correct 6 ms 10076 KB Output is correct
15 Correct 7 ms 9052 KB Output is correct
16 Correct 12 ms 16104 KB Output is correct
17 Correct 13 ms 15960 KB Output is correct
18 Correct 11 ms 16148 KB Output is correct
19 Correct 12 ms 16120 KB Output is correct
20 Correct 12 ms 15964 KB Output is correct