Submission #534715

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
534715	2022-03-08T15:59:28 Z	cig32	Automobil (COCI17_automobil)	C++17	100 / 100	18 ms	2024 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	1868 KB	Output is correct
2	Correct	6 ms	1868 KB	Output is correct
3	Correct	3 ms	1868 KB	Output is correct
4	Correct	5 ms	1868 KB	Output is correct
5	Correct	6 ms	1868 KB	Output is correct
6	Correct	5 ms	1868 KB	Output is correct
7	Correct	9 ms	1868 KB	Output is correct
8	Correct	5 ms	1996 KB	Output is correct
9	Correct	6 ms	1868 KB	Output is correct
10	Correct	9 ms	1868 KB	Output is correct
11	Correct	8 ms	1868 KB	Output is correct
12	Correct	17 ms	1996 KB	Output is correct
13	Correct	6 ms	1940 KB	Output is correct
14	Correct	2 ms	1868 KB	Output is correct
15	Correct	12 ms	1992 KB	Output is correct
16	Correct	18 ms	1996 KB	Output is correct
17	Correct	17 ms	1996 KB	Output is correct
18	Correct	18 ms	2000 KB	Output is correct
19	Correct	18 ms	2024 KB	Output is correct
20	Correct	18 ms	2016 KB	Output is correct