Submission #774606

#	Time	Username	Problem	Language	Result	Execution time	Memory
774606		BidoTeima	Automobil (COCI17_automobil)	C++17	85 / 100	185 ms	39576 KiB

automobil

#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;
      |                    ^~~~~~~

• Subtask 1: 85 / 100