Submission #199950

#TimeUsernameProblemLanguageResultExecution timeMemory
199950mahmoudbadawyAutomobil (COCI17_automobil)C++17
100 / 100
40 ms15992 KiB
#include <bits/stdc++.h>

using namespace std;


const int MOD=1e9+7,N=1e6+5;

long long r[N],c[N];
vector<int> rs,cs;
int n,m,k;
long long inv2;

long long poww(long long b,long long p)
{
	if(p==0) return 1;
	if(p&1) return (b*poww(b,p-1))%MOD;
	return poww((b*b)%MOD,p/2);
}

long long get(long long st,long long en,long long n)
{
	return ((((st+en)%MOD*n)%MOD)*inv2)%MOD;
}

int main()
{
	inv2=poww(2,MOD-2);
	cin >> n >> m >> k;
	for(int i=1;i<=n;i++)
		r[i]=1;
	for(int i=1;i<=m;i++)
		c[i]=1;
	for(int i=0;i<k;i++)
	{
		char x; int a,b;
		cin >> x >> a >> b;
		if(x=='R')
		{
			rs.push_back(a);
			r[a]=(r[a]*b)%MOD;
		}
		else
		{
			cs.push_back(a);
			c[a]=(c[a]*b)%MOD;
		}
	}
	sort(rs.begin(),rs.end()); rs.erase(unique(rs.begin(),rs.end()),rs.end());
	sort(cs.begin(),cs.end()); cs.erase(unique(cs.begin(),cs.end()),cs.end());
	long long ans=0;
	for(int i=1;i<=n;i++)
	{
		ans+=(get(1LL*(i-1)*m+1,1LL*i*m,m)*r[i])%MOD;
		ans%=MOD;
	}
	for(int i=1;i<=m;i++)
	{
		ans+=(get(i,i+1LL*(n-1)*m,n)*(c[i]-1))%MOD;
		ans=(ans+MOD)%MOD;
	}
	for(int i:rs)
	{
		for(int j:cs)
		{
			long long elem=(1LL*(i-1)*m+j)%MOD;
			ans-=(elem*(r[i]+c[j]-1))%MOD;
			ans+=((elem*r[i])%MOD)*c[j];
			ans%=MOD;
			ans=(ans+MOD)%MOD;
		}
	}
	cout << ans << endl;
}
#Verdict Execution timeMemoryGrader output
Fetching results...