oj.uz

Submission #310448

# Submission time Handle Problem Language Result Execution time Memory
310448 2020-10-06T23:58:10 Z Marlov Automobil (COCI17_automobil) C++14
100 / 100
 546 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 power(long long base,long long exp){
	if(exp==1) return base;
	long long save=power(base,exp/2);
	save*=save;
	save%=MOD;
	if(exp%2==1) save*=base;
	return save%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;
}

long long qsum(long long T,long long s,long long e){
	T%=MOD;
	s%=MOD;
	e%=MOD;
	//if(T%2==0) return mult(T*power(2,MOD-2),add(s,e));
	return mult(T,mult(add(s,e),power(2,MOD-2)));
}

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(sub(cm[i],1),(qsum(N,i+1,mult(N-1,M)+i+1))) );
	}
	for(long long i:cols){
		for(long long j:rows){
			long long cv=add(mult(M,j),i+1);
			sum=sub(sum,mult(add(sub(cm[i],1),rm[j]),cv) );
			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
*/

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 16000 KB Output is correct
2 Correct 11 ms 16000 KB Output is correct
3 Correct 10 ms 16000 KB Output is correct
4 Correct 10 ms 16000 KB Output is correct
5 Correct 11 ms 16032 KB Output is correct
6 Correct 10 ms 16000 KB Output is correct
7 Correct 12 ms 16000 KB Output is correct
8 Correct 10 ms 16000 KB Output is correct
9 Correct 11 ms 16000 KB Output is correct
10 Correct 12 ms 16000 KB Output is correct
11 Correct 93 ms 16064 KB Output is correct
12 Correct 298 ms 16120 KB Output is correct
13 Correct 31 ms 16000 KB Output is correct
14 Correct 336 ms 16000 KB Output is correct
15 Correct 307 ms 16120 KB Output is correct
16 Correct 539 ms 16124 KB Output is correct
17 Correct 542 ms 16120 KB Output is correct
18 Correct 543 ms 16120 KB Output is correct
19 Correct 543 ms 16120 KB Output is correct
20 Correct 546 ms 16120 KB Output is correct