Submission #774606

#TimeUsernameProblemLanguageResultExecution timeMemory
774606BidoTeimaAutomobil (COCI17_automobil)C++17
85 / 100
185 ms39576 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const int mod = 1e9 + 7; ll add(ll a, ll b){ return (a + b) % mod; } ll mul(ll a, ll b){ return ((a % mod) * (b % mod)) % mod; } ll sub(ll a, ll b){ return ((a%mod) + mod - (b%mod)) % mod; } #define int long long int32_t main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); ll n,m,k; cin>>n>>m>>k; ll val_row[n], val_col[m], ans = 0; ll coeff_row[n],coeff_col[m]; map<pair<int,int>,ll>coeff; fill(coeff_row, coeff_row+n, 1); fill(coeff_col, coeff_col+m, 1); for(int i = 0; i < n; i++){ val_row[i] = add(mul(mul(i,m),m), m * (m + 1) / 2); ans = add(ans, val_row[i]); } vector<ll>rows,columns; vector<tuple<char, int, int>>queries; for(int i = 0; i < k; i++){ char ch; cin>>ch; int x, y; cin>>x>>y; --x; if(ch == 'R' && find(rows.begin(),rows.end(),x) == rows.end())rows.push_back(x); else if(find(columns.begin(), columns.end(), x) == columns.end())columns.push_back(x); queries.push_back({ch, x, y}); } sort(rows.begin(),rows.end()); sort(columns.begin(),columns.end()); for(int i = 0; i < k; i++){ ll y = get<2>(queries[i]); if(get<0>(queries[i]) == 'R'){ ll row = get<1>(queries[i]); for(int j = 0; j < (int)columns.size(); j++){ ll column = columns[j]; if(coeff.find({row, column}) == coeff.end()){ ll old_val = add(mul(row,m), column + 1); ans = sub(ans, old_val); coeff[{row, column}] = y; ans = add(ans, mul(old_val, y)); }else{ ll p = coeff[{row, column}]; ll old_val = mul(add(mul(row,m), column + 1), p); ans = sub(ans, old_val); coeff[{row, column}] = mul(y, p); ans = add(ans, mul(old_val, y)); } ll l = (j == 0 ? 0 : columns[j - 1] + 1); ll r = (columns[j] - 1); if(l > r)continue; // (row * n + l + 1) + (row * n + l + 2) + (row * n + l + 3) + ... + // (row * n + r + 1) = (row * n * (r - l + 1)) + ((r+1)(r+2)-(l)(l + 1)) / 2; ll old_val = mul(add(mul(mul(row, m), (r - l + 1)), ((r + 1) * (r + 2) - l * (l + 1)) / 2), coeff_row[row]); ans = sub(ans, old_val); ans = add(ans, mul(old_val, y)); } ll l = (columns.empty() ? 0 : columns.back() + 1); ll r = m - 1; if(l > r){ coeff_row[row] = (coeff_row[row] * y) % mod; continue; } ll old_val = mul(add(mul(mul(row, m), (r - l + 1)), ((r + 1) * (r + 2) - l * (l + 1)) / 2), coeff_row[row]); ans = sub(ans, old_val); coeff_row[row] = mul(coeff_row[row], y); ans = add(ans, mul(old_val, y)); }else{ ll column = get<1>(queries[i]); for(int j = 0; j < (int)rows.size(); j++){ ll row = rows[j]; if(coeff.find({row, column}) == coeff.end()){ ll old_val = add(mul(row,m), column + 1); ans = sub(ans, old_val); coeff[{row, column}] = y; ans = add(ans, mul(old_val, y)); }else{ ll p = coeff[{row, column}]; ll old_val = mul(add(mul(row,m), column + 1), p); ans = sub(ans, old_val); coeff[{row, column}] = mul(y, p); ans = add(ans, mul(old_val, y)); } ll l = (j == 0? 0 : rows[j - 1] + 1); ll r = rows[j] - 1; if(l > r) continue; // (m * l + column + 1) + (m * (l + 1) + column + 1) + (m * r + column + 1) ll old_val = mul(add(mul(column + 1, r - l + 1), mul(m, (r * (r + 1) - l * (l - 1)) / 2)), coeff_col[column]); ans = sub(ans, old_val); ans = add(ans, mul(old_val, y)); } ll l = (rows.empty()? 0 : rows.back() + 1); ll r = n - 1; if(l > r) {coeff_col[column]=(coeff_col[column] * y) % mod; continue;} ll old_val = mul(add(mul(column + 1, r - l + 1), mul(m, (r * (r + 1) - l * (l - 1)) / 2)), coeff_col[column]); ans = sub(ans, old_val); coeff_col[column] = mul(coeff_col[column], y); ans = add(ans, mul(old_val, y)); } } cout<<ans; return 0; }

Compilation message (stderr)

automobil.cpp: In function 'int32_t main()':
automobil.cpp:20:20: warning: unused variable 'val_col' [-Wunused-variable]
   20 |     ll val_row[n], val_col[m], ans = 0;
      |                    ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...