답안 #251860

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
251860 2020-07-22T13:02:38 Z leaked Automobil (COCI17_automobil) C++14
100 / 100
397 ms 5820 KB
#include<bits/stdc++.h>
using namespace std;
//#include<ext/pb_ds/assoc_container.hpp>
//#include<ext/pb_ds/tree_policy.hpp>
//
//    #pragma GCC optimize("unroll-loops")
//    #pragma GCC optimize("Ofast")
//    #pragma GCC optimize("-O3")
//    #pragma GCC optimize("no-stack-protector")
//    #pragma GCC optimize("fast-math")
//#define LOCAL
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifndef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
#define fi first
#define f first
#define se second
#define s second
#define vi_a vector<int>a;
#define p_b push_back
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ll long long
typedef unsigned long long ull;
////////////////////////////////???????????????CHECK THIS OUT???????????????//////////////////////////////
#define ld long double
#define pll pair<ll,ll>
#define pii pair<int,int>
#define m_p make_pair
#define fast_io cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
#define all(x) x.begin(),x.end()
#define getfiles    ifstream cin("input.txt");ofstream cout("output.txt");
#define pw(x) (1ll << x)
#define sz(x) (int)x.size()
#define endl "\n"
#define rall(x) x.rbegin(),x.rend()
#define len(a) (ll)a.size()
#define rep(x,l,r) for(ll x=l;x<r;x++)

//using namespace __gnu_pbds;
ld eps = (ld)1 / 1e6;
const ld pi=3.14159265359;
ll inf = 1e18,mod1=1e9+7;
ll sqr(ll a) { return a * a; }
ll qb(ll a) { return a * a * a; }
ll gcd(ll a, ll b) { return !a ? b : gcd(b % a, a); }
ll binpow(ll a, ll b, ll mod) { return b ? (b % 2 ? (a * (sqr(binpow(a, b / 2, mod)) % mod)) % mod : sqr(binpow(a, b / 2, mod)) % mod) : 1; }
ll binmult(ll a, ll b, ll mod) { return b ? (b % 2 ? (2 * binmult(a, b / 2, mod) + a) % mod : (2 * binmult(a, b / 2, mod)) % mod) : 0; }
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
const ll R=1e4;
const ll tx[4]={0,0,-1,1};
const ll ty[4]={-1,1,0,0};
const char rev_to[4]={'E','W','N','S'};
const int N=1e6+1e5;
const int M=1e9+7;
//typedef tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> st;
auto rnd=bind(uniform_int_distribution<ll>(1,1e18),mt19937(time(0)));
ll sub(ll a,ll b){
    return (a-b+M)%M;
}
ll mult(ll a,ll b){
    return binmult(a,b,M);
}
ll add(ll a,ll b){
    return (a+b)%M;
}
ll r[N],c[N];
bool usedr[N],usedc[N];
signed main()
{
    fast_io;
    ll n,m,k;
    cin>>n>>m>>k;
    ll ans=0;
    ll two=binpow(2,M-2,M);
    char cc;ll a2,a1;
    for(int i=0;i<k;i++){
        cin>>cc>>a1>>a2;--a1;
        if(cc=='R'){
            if(!usedr[a1]){
                usedr[a1]=1;
                r[a1]=a2;
            }else r[a1]=mult(r[a1],a2);
        }else{
             if(!usedc[a1]){
                usedc[a1]=1;
                c[a1]=a2;
            }else c[a1]=mult(c[a1],a2);
        }
    }
    vector<pll>lol;
    for(int i=0;i<n;i++){
        if(usedr[i]){
            ll f=(1+i*m),last=(f+m-1);
            ll s=mult(mult(add(f,last),m),two);
            ans=add(ans,mult(s,r[i]));
            lol.p_b({i,r[i]});
        }else{
            ll f=(1+i*m),last=(f+m-1);
            ll s=mult(mult(add(f,last),m),two);
            ans=add(ans,s);
        }
    }
    for(int i=0;i<m;i++){
        if(!usedc[i]) continue;
        ll f=i+1,last=(f+(n-1)*m);
        ll s=mult(mult(add(f,last),n),two);
        for(auto &z : lol){
            ll val=(1+i+z.f*m);
            z.s%=M;
            ll newval=mult(val,z.s);
            s=sub(s,val);
            s=add(s,newval);
        }
        ans=sub(ans,s);
        ans=add(ans,mult(s,c[i]));
    }
    cout<<(ans+M)%M;
    return 0;
}
/*
5  10  15  20
5  6  7  8


/
*/
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 14 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 12 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 24 ms 384 KB Output is correct
8 Correct 7 ms 384 KB Output is correct
9 Correct 20 ms 384 KB Output is correct
10 Correct 26 ms 384 KB Output is correct
11 Correct 76 ms 2048 KB Output is correct
12 Correct 278 ms 4480 KB Output is correct
13 Correct 19 ms 1024 KB Output is correct
14 Correct 272 ms 1016 KB Output is correct
15 Correct 229 ms 4096 KB Output is correct
16 Correct 392 ms 5820 KB Output is correct
17 Correct 387 ms 5752 KB Output is correct
18 Correct 394 ms 5752 KB Output is correct
19 Correct 387 ms 5504 KB Output is correct
20 Correct 397 ms 5752 KB Output is correct