#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(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;
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;
}
# |
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 |
344 KB |
Output is correct |
4 |
Correct |
1 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 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 |
2 ms |
348 KB |
Output is correct |
10 |
Correct |
1 ms |
472 KB |
Output is correct |
11 |
Incorrect |
2 ms |
2912 KB |
Output isn't correct |
12 |
Incorrect |
7 ms |
8796 KB |
Output isn't correct |
13 |
Correct |
1 ms |
860 KB |
Output is correct |
14 |
Incorrect |
8 ms |
10076 KB |
Output isn't correct |
15 |
Incorrect |
7 ms |
9064 KB |
Output isn't correct |
16 |
Incorrect |
12 ms |
15964 KB |
Output isn't correct |
17 |
Incorrect |
14 ms |
15964 KB |
Output isn't correct |
18 |
Incorrect |
12 ms |
15964 KB |
Output isn't correct |
19 |
Incorrect |
12 ms |
15964 KB |
Output isn't correct |
20 |
Incorrect |
12 ms |
15964 KB |
Output isn't correct |