답안 #309886

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
309886 2020-10-04T21:58:31 Z Marlov Automobil (COCI17_automobil) C++14
85 / 100
37 ms 16124 KB
/*
Code by @marlov       
*/
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <string>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <utility>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <stack>
#include <queue>
#include <iterator>
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;
}

long long add(long long a,long long b){
	a+=b;
	while(a<0) a+=MOD;
	return a%MOD;
}
long long sub(long long a,long long b){
	a-=b;
	while(a<0) a+=MOD;
	return a%MOD;
}
long long mult(long long a,long long b){
	a*=b;
	return a%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]=mult(rm[x],m);
		}else if(c=='S'){
			cols.insert(x);
			cm[x]=mult(cm[x],m);
		}
	}
	for(long long i=0;i<N;i++){
		sum=add( sum , mult(rm[i],(qsum(M,mult(i,M)+1,mult(i,M)+M))) );
	}
	for(long long i=0;i<M;i++){
		sum=add(sum, mult((cm[i]-1),(qsum(N,i+1,mult(N-1,M)+i+1))) );
	}
	//cout<<"2nd: "<<sum<<'\n';
	for(long long i:cols){
		for(long long j:rows){
			long long cv=(M*j+i+1)%MOD;
			sum=sub(sum,mult(add(cm[i]-1,rm[j]),cv) );
			//sum+=MOD;
			sum=add(sum, mult( mult(cm[i],rm[j]), cv) );
		}
	}
	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
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 16000 KB Output is correct
2 Correct 10 ms 16000 KB Output is correct
3 Correct 9 ms 16000 KB Output is correct
4 Correct 9 ms 16000 KB Output is correct
5 Correct 9 ms 16000 KB Output is correct
6 Correct 9 ms 16000 KB Output is correct
7 Correct 10 ms 16000 KB Output is correct
8 Correct 9 ms 16000 KB Output is correct
9 Correct 10 ms 16000 KB Output is correct
10 Correct 11 ms 16000 KB Output is correct
11 Incorrect 15 ms 16000 KB Output isn't correct
12 Correct 26 ms 15872 KB Output is correct
13 Incorrect 11 ms 16000 KB Output isn't correct
14 Incorrect 23 ms 16000 KB Output isn't correct
15 Correct 25 ms 16000 KB Output is correct
16 Correct 37 ms 16120 KB Output is correct
17 Correct 36 ms 16120 KB Output is correct
18 Correct 37 ms 16124 KB Output is correct
19 Correct 35 ms 16000 KB Output is correct
20 Correct 36 ms 16000 KB Output is correct