Submission #534715

#	Time	Username	Problem	Language	Result	Execution time	Memory
534715		cig32	Automobil (COCI17_automobil)	C++17	100 / 100	18 ms	2024 KiB

automobil

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) { 
  if(p==0) return 1;
  int r = bm(b, p/2);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) {
  return bm(b, MOD-2);
}
int f[MAXN];
int nCr(int n, int r) { 
  int ans = f[n]; ans *= inv(f[r]); ans %= MOD;
  ans *= inv(f[n-r]); ans %= MOD; return ans;
}

void precomp() { 
  f[0] = 1;
  for(int i=1; i<MAXN; i++) f[i] = (f[i-1] * i) % MOD;
}

void solve(int tc) {
  int a, b, c;
  cin >> a >> b >> c;
  __int128 n, m, k;
  n = a, m = b, k = c;
  map<__int128, __int128> row, col;
  map<int, bool> er, ec;
  for(int i=0; i<k; i++) {
    char c; cin >> c;
    int x, y; cin >> x >> y;
    if(c == 'R') row[x] = (er[x] ? (y * row[x]) % MOD : y);
    else col[x] = (ec[x] ? (y * col[x]) % MOD : y);
    if(c == 'R') er[x] = 1;
    else ec[x] = 1;
  }
  __int128 tot = n*m;
  tot %= MOD;
  tot *= (n*m + 1);
  tot %= MOD;
  tot *= inv(2);
  tot %= MOD;
  for(auto x: row) {
    __int128 st = (x.first - 1) * m + 1;
    __int128 en = (x.first - 1) * m + m;
    __int128 pot = (st + en) * m / 2;
    pot %= MOD;
    tot = (tot + MOD - pot) % MOD;

    pot *= x.second;
    pot %= MOD;
    tot = (tot + pot) % MOD;
  }
  for(auto x: col) {
    __int128 st = x.first;
    __int128 en = (n - 1) * m + x.first;
    __int128 pot = (st + en) * n / 2;
    pot %= MOD;
    tot = (tot + MOD - pot) % MOD;

    pot *= x.second;
    pot %= MOD;
    tot = (tot + pot) % MOD;
  }
  for(auto x: row) {
    for(auto y: col) {
      __int128 uwu = (x.first - 1) * m + y.first;
      uwu %= MOD;
      tot = (tot + uwu) % MOD;
      __int128 old = uwu;
      uwu *= x.second;
      uwu %= MOD;
      tot = (tot + MOD - uwu) % MOD;
      uwu = old;

      uwu *= y.second;
      uwu %= MOD;
      tot = (tot + MOD - uwu) % MOD;

      uwu *= x.second;
      uwu %= MOD;
      tot = (tot + uwu) % MOD;
    }
  }
  cout << (long long)tot << '\n';
}
int32_t main(){
  precomp();
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

• Subtask 1: 100 / 100