#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/rope>
#define MEM(a, b) memset(a, (b), sizeof(a))
#define ALL(c) (c).begin(),(c).end()
#define sz(a) ((int)(a.size()))
#define ll long long
#define LINF (ll)1e18
#define INF (int)1e9
#define MINF 0x3F3F3F3F
#define pb push_back
#define fs first
#define sc second
#define mp make_pair
#define MOD 1000000007
#define IO ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define MAX 1000005
#define watch(x) cerr<<#x<<" = "<<(x)<<endl;
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
template<class T> using indexed_set = tree<T, null_type, less<T>, rb_tree_tag,tree_order_statistics_node_update>;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
ll sol;
ll n, m, k, x, y;
ll sum_w;
char c;
vector<pll> upd_r, upd_c;
map<ll,ll> Mr, Mc;
inline ll mult(ll a, ll b) {
return (a*b)%MOD;
}
inline ll add(ll a, ll b) {
return (a+b+MOD)%MOD;
}
inline ll gauss(ll from, ll to, ll nums) {
return mult( add(from, to) , nums )>>1;
}
inline ll val(ll y, ll x) {
return add( mult(y-1, m),x);
}
int main() {
cin >> n >> m >> k;
for(int i=0;i<k;i++) {
cin >> c >> x >> y;
if(c=='R') {
if(Mr.find(x)==Mr.end()) Mr[x] = y;
else Mr[x] *= y;
}
else {
if(Mc.find(x)==Mc.end()) Mc[x] = y;
else Mc[x] *= y;
}
}
for(auto x:Mr) upd_r.pb(mp(x.first,x.second));
for(auto x:Mc) upd_c.pb(mp(x.first,x.second));
sort(ALL(upd_r)); sort(ALL(upd_c));
for(int i=0;i<sz(upd_c);i++) {
ll col = upd_c[i].fs;
ll col_up = upd_c[i].sc;
ll last_row = 1;
for(int j=0;j<sz(upd_r);j++) {
ll row = upd_r[j].fs;
ll row_up = upd_r[j].sc;
if(row==last_row) {
ll c = val(row, col);
sol = add(sol, mult(c, mult(col_up,row_up) ) );
sum_w = add(sum_w, c);
last_row = row+1;
continue;
}
else if(row==last_row+1) {
ll c = val(last_row, col);
sol = add(sol, mult(c,col_up) );
sum_w = add(sum_w, c);
last_row = row+1;
}
else {
ll cl = val(last_row, col);
ll ch = val(row-1, col);
ll sum_range = gauss(cl, ch, row-last_row);
ll mult_range = mult(sum_range, col_up);
sol = add(sol, mult_range);
sum_w = add(sum_w, sum_range);
last_row = row+1;
}
ll c = val(row, col);
sol = add(sol, mult(c, mult(col_up,row_up) ) );
sum_w = add(sum_w, c);
last_row = row+1;
}
if(last_row>n) continue;
else if(last_row==n) {
ll c = val(n, col);
sol = add(sol, mult(c, col_up) );
sum_w = add(sum_w, c);
}
else {
ll cl = val(last_row, col);
ll ch = val(n, col);
ll sum_range = gauss(cl, ch, n-last_row+1);
ll mult_range = mult(sum_range, col_up);
sol = add(sol, mult_range);
sum_w = add(sum_w, sum_range);
}
}
for(int i=0;i<sz(upd_r);i++) {
ll row = upd_r[i].fs;
ll row_up = upd_r[i].sc; ll last_col = 1;
for(int j=0;j<sz(upd_c);j++) {
ll col = upd_c[j].fs;
ll col_up = upd_c[j].sc;
if(last_col==col) {
last_col = col + 1;
continue;
}
else if(col==last_col+1) {
ll c = val(row, last_col);
sol = add(sol, mult(c,row_up) );
sum_w = add(sum_w, c);
last_col = col + 1;
continue;
}
else {
ll cl = val(row, last_col);
ll ch = val(row, col-1);
ll sum_range = gauss(cl, ch, col-last_col);
ll mult_range = mult(sum_range, row_up);
sol = add(sol, mult_range);
sum_w = add(sum_w, sum_range);
last_col = col+1;
}
}
if(last_col>m) continue;
else if(last_col==m) {
ll c = val(row, m);
sol = add(sol, mult(c,row_up) );
sum_w = add(sum_w, c);
}
else {
ll cl = val(row,last_col);
ll ch = val(row, m);
ll sum_range = gauss(cl, ch, m-last_col+1);
ll mult_range = mult(sum_range, row_up);
sol = add(sol, mult_range);
sum_w = add(sum_w, sum_range);
}
}
ll t = mult(n, m);
ll total_no_update = mult(t, t+1)>>1;
ll res = total_no_update - sum_w;
cout << add(sol, res);
return 0;
}
Compilation message
automobil.cpp: In function 'int main()':
automobil.cpp:127:7: warning: unused variable 'col_up' [-Wunused-variable]
ll col_up = upd_c[j].sc;
^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 2 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
| 3 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 4 |
Incorrect |
4 ms |
376 KB |
Output isn't correct |
| 5 |
Incorrect |
3 ms |
404 KB |
Output isn't correct |
| 6 |
Incorrect |
3 ms |
376 KB |
Output isn't correct |
| 7 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 8 |
Incorrect |
4 ms |
380 KB |
Output isn't correct |
| 9 |
Incorrect |
5 ms |
372 KB |
Output isn't correct |
| 10 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 11 |
Incorrect |
8 ms |
376 KB |
Output isn't correct |
| 12 |
Incorrect |
18 ms |
376 KB |
Output isn't correct |
| 13 |
Incorrect |
6 ms |
376 KB |
Output isn't correct |
| 14 |
Incorrect |
2 ms |
256 KB |
Output isn't correct |
| 15 |
Incorrect |
13 ms |
376 KB |
Output isn't correct |
| 16 |
Incorrect |
19 ms |
504 KB |
Output isn't correct |
| 17 |
Incorrect |
19 ms |
376 KB |
Output isn't correct |
| 18 |
Incorrect |
19 ms |
376 KB |
Output isn't correct |
| 19 |
Incorrect |
19 ms |
376 KB |
Output isn't correct |
| 20 |
Incorrect |
19 ms |
376 KB |
Output isn't correct |
