#include <bits/stdc++.h>
using namespace std;
#define int long long
const int const1 = 1e9 + 7;
int power(int a, int b)
{
if(b == 0)
{
return 1;
}
else if(b % 2 == 0)
{
int t = power(a, b / 2);
return t * t % const1;
}
else
{
int t= power(a, b / 2);
t = t * t % const1;
return t * a % const1;
}
}
signed main()
{
int n, m, k;
cin >> n >> m >> k;
int inv2 = power(2, const1 - 2);
int ans = n * m % const1 * (n * m % const1 + 1) % const1 * inv2 % const1;
vector <pair <int, int> > p1, p2;
vector <pair <int, int> > pointsx, pointsy;
for(int i = 0; i < k; i++)
{
char t;
cin >> t;
int x, y;
cin >> x >> y;
if(t == 'R')
{
p1.push_back({x, y});
}
else
{
p2.push_back({x, y});
}
}
sort(p1.begin(), p1.end());
sort(p2.begin(), p2.end());
for(int i = 0; i < p1.size(); i++)
{
for(int j = 0; j < p2.size(); j++)
{
pointsx.push_back({p1[i].first, p2[j].first});
pointsy.push_back({p2[j].first, p1[i].first});
}
}
sort(pointsx.begin(), pointsx.end());
sort(pointsy.begin(), pointsy.end());
int X = unique(pointsx.begin(), pointsx.end()) - pointsx.begin();
int Y = unique(pointsy.begin(), pointsy.end()) - pointsy.begin();
int iter = 0;
for(int i = 0; i < p1.size(); i++)
{
int j = i;
int p = 1;
while(j < p1.size() && p1[j].first == p1[i].first)
{
p = p * p1[j].second % const1;
j++;
}
int sum1 = 0;
while(iter < X && pointsx[iter].first < p1[i].first)
{
iter++;
}
while(iter < X && pointsx[iter].first == p1[i].first)
{
sum1 += (pointsx[iter].first - 1) * m + pointsx[iter].second;
sum1 %= const1;
iter++;
}
sum1 %= const1;
sum1 = ((m * (p1[i].first - 1) * 2 + m + 1) % const1) * m % const1 * inv2 % const1 - sum1;
if(sum1 < 0)
{
sum1 += const1;
}
ans = ans - sum1;
if(ans < 0)
{
ans += const1;
}
ans = (ans + sum1 * p) % const1;
p1[i].second = p;
i = j - 1;
}
iter = 0;
for(int i = 0; i < p2.size(); i++)
{
int j = i;
int p = 1;
while(j < p2.size() && p2[j].first == p2[i].first)
{
p = p * p2[j].second % const1;
j++;
}
int sum1 = 0;
while(iter < Y && pointsy[iter].first < p2[i].first)
{
iter++;
}
while(iter < Y && pointsy[iter].first == p2[i].first)
{
sum1 += pointsy[iter].first + (pointsy[iter].second - 1) * (m);
sum1 %= const1;
iter++;
}
sum1 = (((n - 1) * m % const1 + 2 * p2[i].first) * n % const1) * inv2 % const1 - sum1;
if(sum1 < 0)
{
sum1 += const1;
}
ans = ans - sum1;
if(ans < 0)
{
ans += const1;
}
ans = (ans + sum1 * p) % const1;
p2[i].second = p;
i = j - 1;
}
for(int i = 0; i < X; i++)
{
int val = (pointsx[i].first - 1) * (m) + pointsx[i].second;
val %= const1;
ans -= val;
if(ans < 0)
{
ans += const1;
}
int it1 = lower_bound(p1.begin(), p1.end(), make_pair(pointsx[i].first, 0LL)) - p1.begin();
int it2 = lower_bound(p2.begin(), p2.end(), make_pair(pointsx[i].second, 0LL)) - p2.begin();
val = val * p1[it1].second % const1 * p2[it2].second % const1;
ans += val;
if(ans >= const1)
{
ans -= const1;
}
}
cout << ans;
return 0;
}
Compilation message
automobil.cpp: In function 'int main()':
automobil.cpp:48:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < p1.size(); i++)
~~^~~~~~~~~~~
automobil.cpp:50:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < p2.size(); j++)
~~^~~~~~~~~~~
automobil.cpp:61:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < p1.size(); i++)
~~^~~~~~~~~~~
automobil.cpp:65:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < p1.size() && p1[j].first == p1[i].first)
~~^~~~~~~~~~~
automobil.cpp:97:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < p2.size(); i++)
~~^~~~~~~~~~~
automobil.cpp:101:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j < p2.size() && p2[j].first == p2[i].first)
~~^~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
1020 KB |
Output is correct |
| 2 |
Correct |
26 ms |
3640 KB |
Output is correct |
| 3 |
Correct |
6 ms |
640 KB |
Output is correct |
| 4 |
Correct |
37 ms |
6676 KB |
Output is correct |
| 5 |
Correct |
20 ms |
3612 KB |
Output is correct |
| 6 |
Correct |
10 ms |
1316 KB |
Output is correct |
| 7 |
Correct |
35 ms |
6708 KB |
Output is correct |
| 8 |
Correct |
14 ms |
2084 KB |
Output is correct |
| 9 |
Correct |
29 ms |
3768 KB |
Output is correct |
| 10 |
Correct |
43 ms |
6712 KB |
Output is correct |
| 11 |
Correct |
24 ms |
3516 KB |
Output is correct |
| 12 |
Correct |
61 ms |
7724 KB |
Output is correct |
| 13 |
Correct |
17 ms |
2076 KB |
Output is correct |
| 14 |
Correct |
5 ms |
384 KB |
Output is correct |
| 15 |
Correct |
46 ms |
6676 KB |
Output is correct |
| 16 |
Correct |
65 ms |
8372 KB |
Output is correct |
| 17 |
Correct |
65 ms |
8496 KB |
Output is correct |
| 18 |
Correct |
70 ms |
8368 KB |
Output is correct |
| 19 |
Correct |
65 ms |
8368 KB |
Output is correct |
| 20 |
Correct |
67 ms |
8372 KB |
Output is correct |
