답안 #544327

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
544327 2022-04-01T16:55:13 Z SmolBrain Automobil (COCI17_automobil) C++17
100 / 100
26 ms 23820 KB
// Om Namah Shivaya
// GM in 123 days

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define endl '\n'
#define pb push_back
#define conts continue
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "YES" << endl
#define no cout << "NO" << endl
#define ff first
#define ss second
#define ceil2(x,y) ((x+y-1) / (y))
#define sz(a) a.size()
#define setbits(x) __builtin_popcountll(x)
#ifndef ONLINE_JUDGE
#define debug(x) cout << #x <<" = "; print(x); cout << endl
#else
#define debug(x)
#endif

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

bool iseven(ll n) {if ((n & 1) == 0) return true; return false;}

void print(ll t) {cout << t;}
void print(int t) {cout << t;}
void print(string t) {cout << t;}
void print(char t) {cout << t;}
void print(double t) {cout << t;}
void print(ld t) {cout << t;}

template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T, class V> void print(pair <T, V> p) {cout << "{"; print(p.ff); cout << ","; print(p.ss); cout << "}";}
template <class T> void print(vector <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(set <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T> void print(multiset <T> v) {cout << "[ "; for (T i : v) {print(i); cout << " ";} cout << "]";}
template <class T, class V> void print(map <T, V> v) {cout << "[ "; for (auto i : v) {print(i); cout << " ";} cout << "]";}
template<typename T> void amin(T &a, T b) { a = min(a, b); }
template<typename T> void amax(T &a, T b) { a = max(a, b); }

void usaco(string filename) {
    freopen((filename + ".in").c_str(), "r", stdin);
    freopen((filename + ".out").c_str(), "w", stdout);
}

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 5;
const int inf1 = 1e9 + 5;
const ll inf2 = ll(1e18) + 5;

void solve(int test_case)
{
    /*

    https://ideone.com/Ejf10T => though my sol idea is not similar to this code,
    i got the ideas for building the sol from this code

    sol idea: initially do all the row operations, then modify the column sum 'colsum' values and then do the column operations

    val = the initial value written on a given cell
    colsum[j] = sum of all cells in column j, initially stores the sum of all the initial values written on the cells in column j

    modifying the 'colsum' array: colsum[j] - val + val * rowmul[i] = colsum[j] + val * (rowmul[i] - 1)

    when moving from col to col + 1, the summation of val * (rowmul[i] - 1) over all i
    increases by 'sum', where sum = the sum of (rowmul[i] - 1) over all i
    this is because the value 'val' of all cells increase by 1 when u go from col to col + 1
    (val + 1) * (rowmul[i] - 1) - val * (rowmul[i] - 1) = rowmul[i] - 1

    */

    ll n, m, k; cin >> n >> m >> k;

    vector<ll> rowmul(n + 5, 1), colmul(m + 5, 1);

    rep1(i, k) {
        char ch; cin >> ch;
        ll x, y; cin >> x >> y;

        if (ch == 'R') rowmul[x] = (rowmul[x] * y) % MOD;
        else colmul[x] = (colmul[x] * y) % MOD;
    }

    auto get = [&](ll i, ll j) {
        return ((i - 1) * m + j) % MOD;
    };

    auto apsum = [&](ll a, ll d) {
        // 0.5n*(2a + (n - 1)d)
        ll res = n * (2 * a + (n - 1) * d);
        res /= 2;
        res %= MOD;
        return res;
    };

    vector<ll> colsum(m + 5);
    rep1(j, m) {
        colsum[j] = apsum(j, m);
    }

    ll sum = 0, curr = 0;
    rep1(i, n) {
        sum += rowmul[i] - 1;
        sum %= MOD;

        ll temp = (get(i, 1) * (rowmul[i] - 1) % MOD + MOD) % MOD;
        curr = (curr + temp) % MOD;
    }

    ll ans = 0;

    rep1(j, m) {
        colsum[j] = (colsum[j] + curr + MOD) % MOD;
        ll toadd = colsum[j] * colmul[j] % MOD;
        ans = (ans + toadd) % MOD;
        curr = (curr + sum) % MOD;
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    // cin >> t;
    rep1(i, t) {
        solve(i);
    }

    return 0;
}

Compilation message

automobil.cpp: In function 'void usaco(std::string)':
automobil.cpp:64:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   64 |     freopen((filename + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
automobil.cpp:65:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   65 |     freopen((filename + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 4 ms 3796 KB Output is correct
12 Correct 13 ms 11732 KB Output is correct
13 Correct 2 ms 1236 KB Output is correct
14 Correct 16 ms 13140 KB Output is correct
15 Correct 13 ms 12884 KB Output is correct
16 Correct 25 ms 23764 KB Output is correct
17 Correct 25 ms 23816 KB Output is correct
18 Correct 25 ms 23820 KB Output is correct
19 Correct 26 ms 23768 KB Output is correct
20 Correct 24 ms 23756 KB Output is correct