제출 #309821

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
309821		updown1	Automobil (COCI17_automobil)	C++17	85 / 100	25 ms	16000 KiB

automobil

/*
Code by @marlov       
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<long long,long long> pi;
 
#define maxV 1000002
#define MOD 1000000007
//const long long MOD=1000000007;
long long N,M,K;
long long sum=0;
unordered_set<long long> cols;
unordered_set<long long> rows;
long long cm[maxV];
long long rm[maxV];
 
long long qsum(long long T,long long s,long long e){
  T %= MOD;
  s %= MOD;
  e %= MOD;
	if(T%2==0) return ((T/2)*(s+e))%MOD;
	else return (((s+e)/2)*(T))%MOD;
}
 
void add(long long v){
	sum+=v;
	sum%=MOD;
	while(sum<0) sum+=MOD;
}
void sub(long long v){
	sum-=v;
	sum%=MOD;
	while(sum<0) sum+=MOD;
}
void mult(long long v){
	sum*=v;
	sum%=MOD;
}
 
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>N>>M>>K;
	fill(cm,cm+maxV,1);
	fill(rm,rm+maxV,1);
	char c;
	long long x,m;
	for(long long i=0;i<K;i++){
		cin>>c>>x>>m;
		x--;
		if(c=='R'){
			rows.insert(x);
			rm[x]*=m;
			rm[x]%=MOD;
		}else if(c=='S'){
			cols.insert(x);
			cm[x]*=m;
			cm[x]%=MOD;
		}
	}
	for(long long i=0;i<N;i++){
		add(rm[i]*(qsum(M,i*M+1,i*M+M)));
		//sum+=MOD;
	}
	//cout<<"1st: "<<sum<<'\n';
	for(long long i:cols){
		//cout<<(qsum(N,i+1,(N-1)*M+i+1))<<'\n';
		add((cm[i]-1)*(qsum(N,i+1,(N-1)*M+i+1)));
		//sum+=MOD;
	}
	//cout<<"2nd: "<<sum<<'\n';
	for(long long i:cols){
		for(long long j:rows){
			long long cv= (M*j+i+1)%MOD;
			sub((cm[i]+rm[j]-1)*cv);
			//sum+=MOD;
          assert(sum >= 0);
			add(((cm[i]*rm[j])%MOD)*cv);
		}
	}
  assert(sum >= 0 && sum < MOD);
	cout<<sum<<'\n';
    return 0;
}
 
/* stuff you should look for
	* long long overflow, array bounds
	* special cases (n=1,n=0?)
	* do smth instead of nothing and stay organized
*/

• Subtask 1: 85 / 100