Submission #309822

#	Time	Username	Problem	Language	Result	Execution time	Memory
309822		Marlov	Miners (IOI07_miners)	C++14	0 / 100	12 ms	16032 KiB

miners

/*
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;
}

void add(long long v){
	sum+=v;
	sum%=MOD;
	while(sum<0) sum+=MOD;
	sum%=MOD;
}
void sub(long long v){
	sum-=v;
	sum%=MOD;
	while(sum<0) sum+=MOD;
	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=0;i<M;i++){
		//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;
			add((((cm[i]*rm[j])%MOD)*cv)%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: 0 / 9
• Subtask 2: 0 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 9
• Subtask 5: 0 / 9
• Subtask 6: 0 / 7
• Subtask 7: 0 / 8
• Subtask 8: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8