#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
ll add(ll a, ll b){
return (a + b) % mod;
}
ll mul(ll a, ll b){
return ((a % mod) * (b % mod)) % mod;
}
ll sub(ll a, ll b){
return ((a%mod) + mod - (b%mod)) % mod;
}
#define int long long
int32_t main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
ll n,m,k;
cin>>n>>m>>k;
ll val_row[n], val_col[m], ans = 0;
ll coeff_row[n],coeff_col[m];
map<pair<int,int>,ll>coeff;
fill(coeff_row, coeff_row+n, 1);
fill(coeff_col, coeff_col+m, 1);
for(int i = 0; i < n; i++){
val_row[i] = add(mul(mul(i,m),m), m * (m + 1) / 2);
ans = add(ans, val_row[i]);
}
vector<ll>rows,columns;
vector<tuple<char, int, int>>queries;
for(int i = 0; i < k; i++){
char ch;
cin>>ch;
int x, y;
cin>>x>>y;
--x;
if(ch == 'R' && find(rows.begin(),rows.end(),x) == rows.end())rows.push_back(x);
else if(find(columns.begin(), columns.end(), x) == columns.end())columns.push_back(x);
queries.push_back({ch, x, y});
}
sort(rows.begin(),rows.end());
sort(columns.begin(),columns.end());
for(int i = 0; i < k; i++){
ll y = get<2>(queries[i]);
if(get<0>(queries[i]) == 'R'){
ll row = get<1>(queries[i]);
for(int j = 0; j < (int)columns.size(); j++){
ll column = columns[j];
if(coeff.find({row, column}) == coeff.end()){
ll old_val = add(mul(row,m), column + 1);
ans = sub(ans, old_val);
coeff[{row, column}] = y;
ans = add(ans, mul(old_val, y));
}else{
ll p = coeff[{row, column}];
ll old_val = mul(add(mul(row,m), column + 1), p);
ans = sub(ans, old_val);
coeff[{row, column}] = mul(y, p);
ans = add(ans, mul(old_val, y));
}
ll l = (j == 0 ? 0 : columns[j - 1] + 1);
ll r = (columns[j] - 1);
if(l > r)continue;
// (row * n + l + 1) + (row * n + l + 2) + (row * n + l + 3) + ... +
// (row * n + r + 1) = (row * n * (r - l + 1)) + ((r+1)(r+2)-(l)(l + 1)) / 2;
ll old_val = mul(add(mul(mul(row, m), (r - l + 1)), ((r + 1) * (r + 2) - l * (l + 1)) / 2), coeff_row[row]);
ans = sub(ans, old_val);
ans = add(ans, mul(old_val, y));
}
ll l = (columns.empty() ? 0 : columns.back() + 1);
ll r = m - 1;
if(l > r){ coeff_row[row] = (coeff_row[row] * y) % mod; continue; }
ll old_val = mul(add(mul(mul(row, m), (r - l + 1)), ((r + 1) * (r + 2) - l * (l + 1)) / 2), coeff_row[row]);
ans = sub(ans, old_val);
coeff_row[row] = mul(coeff_row[row], y);
ans = add(ans, mul(old_val, y));
}else{
ll column = get<1>(queries[i]);
for(int j = 0; j < (int)rows.size(); j++){
ll row = rows[j];
if(coeff.find({row, column}) == coeff.end()){
ll old_val = add(mul(row,m), column + 1);
ans = sub(ans, old_val);
coeff[{row, column}] = y;
ans = add(ans, mul(old_val, y));
}else{
ll p = coeff[{row, column}];
ll old_val = mul(add(mul(row,m), column + 1), p);
ans = sub(ans, old_val);
coeff[{row, column}] = mul(y, p);
ans = add(ans, mul(old_val, y));
}
ll l = (j == 0? 0 : rows[j - 1] + 1);
ll r = rows[j] - 1;
if(l > r) continue;
// (m * l + column + 1) + (m * (l + 1) + column + 1) + (m * r + column + 1)
ll old_val = mul(add(mul(column + 1, r - l + 1), mul(m, (r * (r + 1) - l * (l - 1)) / 2)), coeff_col[column]);
ans = sub(ans, old_val);
ans = add(ans, mul(old_val, y));
}
ll l = (rows.empty()? 0 : rows.back() + 1);
ll r = n - 1;
if(l > r) {coeff_col[column]=(coeff_col[column] * y) % mod; continue;}
ll old_val = mul(add(mul(column + 1, r - l + 1), mul(m, (r * (r + 1) - l * (l - 1)) / 2)), coeff_col[column]);
ans = sub(ans, old_val);
coeff_col[column] = mul(coeff_col[column], y);
ans = add(ans, mul(old_val, y));
}
}
cout<<ans;
return 0;
}
Compilation message
automobil.cpp: In function 'int32_t main()':
automobil.cpp:20:20: warning: unused variable 'val_col' [-Wunused-variable]
20 | ll val_row[n], val_col[m], ans = 0;
| ^~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
6 ms |
724 KB |
Output is correct |
| 2 |
Correct |
39 ms |
4332 KB |
Output is correct |
| 3 |
Correct |
3 ms |
596 KB |
Output is correct |
| 4 |
Correct |
29 ms |
1612 KB |
Output is correct |
| 5 |
Incorrect |
29 ms |
3532 KB |
Output isn't correct |
| 6 |
Correct |
14 ms |
1608 KB |
Output is correct |
| 7 |
Incorrect |
60 ms |
5820 KB |
Output isn't correct |
| 8 |
Incorrect |
16 ms |
1988 KB |
Output isn't correct |
| 9 |
Correct |
46 ms |
4928 KB |
Output is correct |
| 10 |
Correct |
70 ms |
7116 KB |
Output is correct |
| 11 |
Correct |
42 ms |
8960 KB |
Output is correct |
| 12 |
Correct |
136 ms |
28640 KB |
Output is correct |
| 13 |
Correct |
27 ms |
4308 KB |
Output is correct |
| 14 |
Correct |
14 ms |
16852 KB |
Output is correct |
| 15 |
Correct |
95 ms |
23924 KB |
Output is correct |
| 16 |
Correct |
185 ms |
39576 KB |
Output is correct |
| 17 |
Correct |
154 ms |
39436 KB |
Output is correct |
| 18 |
Correct |
160 ms |
39372 KB |
Output is correct |
| 19 |
Correct |
154 ms |
39392 KB |
Output is correct |
| 20 |
Correct |
160 ms |
39496 KB |
Output is correct |
