/**Lucky Boy**/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pb push_back
#define mp make_pair
#define F first
#define S second
#define maxc 1000000007
#define maxn 100005
#define maxm 500005
#define pii pair <long long,long long>
#define Task "Automobil"
template <typename T> inline void read(T &x){char c;bool nega=0;while((!isdigit(c=getchar()))&&(c!='-'));if(c=='-'){nega=1;c=getchar();}x=c-48;while(isdigit(c=getchar())) x=x*10+c-48;if(nega) x=-x;}
template <typename T> inline void writep(T x){if(x>9) writep(x/10);putchar(x%10+48);}
template <typename T> inline void write(T x){if(x<0){putchar('-');x=-x;}writep(x);putchar(' ');}
template <typename T> inline void writeln(T x){write(x);putchar('\n');}
using namespace std;
long long ans,n,m,q,ta,tb;
pii a[1003],b[1003];
void Recode(pii x[],long long &sz)
{
sort(x+1,x+sz+1);
long long cnt = 0;
FOR(i,1,sz)
{
long long cur = 1,r = i;
while (r <= sz && x[r].F == x[i].F)
{
cur = (1ll*cur*x[r].S) % maxc;
++r;
}
x[++cnt] = mp(x[i].F,cur);
i = r - 1;
}
sz = cnt;
}
long long Get(long long l,long long r,long long dis)
{
long long res;
long long ssh = (r - l) / dis + 1;
if (ssh % 2 == 1)
{
res = ((l+r) / 2) % maxc;
ssh %= maxc;
res = res * ssh % maxc;
}
else
{
res = (ssh / 2) % maxc;
res %= maxc;
r = (l + r) % maxc;
res = res * r % maxc;
}
return res;
}
int main()
{
ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
//freopen(Task".inp", "r",stdin);
//freopen(Task".out", "w",stdout);
cin >> n >> m >> q;
FOR(i,1,q)
{
char c;
long long x,y;
cin >> c >> x >> y;
if (c == 'R') a[++ta] = mp(x,y);
else b[++tb] = mp(x,y);
}
Recode(a,ta);
Recode(b,tb);
ans = Get(1,n*m,1);
FOR(i,1,ta)
{
long long sum = Get(1ll*m*a[i].F - m + 1,1ll*m*a[i].F,1);
ans = (ans - sum + maxc) % maxc;
sum = (sum * a[i].S) % maxc;
ans = (ans + sum) % maxc;
}
FOR(i,1,tb)
{
long long sum = Get(b[i].F,b[i].F + 1ll*(n-1)*m,m);
ans = (ans - sum + maxc) % maxc;
sum = (sum * b[i].S) % maxc;
ans = (ans + sum) % maxc;
}
FOR(i,1,ta)
FOR(j,1,tb)
{
long long u = a[i].F,v = b[j].F;
long long old = (1ll*(u-1)*m + v) % maxc;
long long ne = (old * b[j].S) % maxc;
ans = (ans - ne + old + maxc) % maxc;
old = (old * a[i].S) % maxc;
ne = (old * b[j].S) % maxc;
ans = (ans - old + ne + maxc) % maxc;
}
cout << ans;
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
376 KB |
Output is correct |
| 2 |
Correct |
3 ms |
380 KB |
Output is correct |
| 3 |
Correct |
2 ms |
424 KB |
Output is correct |
| 4 |
Correct |
3 ms |
500 KB |
Output is correct |
| 5 |
Correct |
3 ms |
576 KB |
Output is correct |
| 6 |
Correct |
3 ms |
592 KB |
Output is correct |
| 7 |
Correct |
4 ms |
592 KB |
Output is correct |
| 8 |
Correct |
2 ms |
592 KB |
Output is correct |
| 9 |
Correct |
3 ms |
592 KB |
Output is correct |
| 10 |
Correct |
3 ms |
592 KB |
Output is correct |
| 11 |
Correct |
3 ms |
596 KB |
Output is correct |
| 12 |
Correct |
6 ms |
620 KB |
Output is correct |
| 13 |
Correct |
3 ms |
620 KB |
Output is correct |
| 14 |
Correct |
2 ms |
620 KB |
Output is correct |
| 15 |
Correct |
5 ms |
620 KB |
Output is correct |
| 16 |
Correct |
6 ms |
620 KB |
Output is correct |
| 17 |
Correct |
6 ms |
636 KB |
Output is correct |
| 18 |
Correct |
6 ms |
636 KB |
Output is correct |
| 19 |
Correct |
7 ms |
636 KB |
Output is correct |
| 20 |
Correct |
6 ms |
636 KB |
Output is correct |
