oj.uz

Submission #1097063

# Submission time Handle Problem Language Result Execution time Memory
1097063 2024-10-06T02:50:08 Z vjudge1 Automobil (COCI17_automobil) C++17
55 / 100
 1000 ms 8532 KB 
#include <bits/stdc++.h>
using namespace std;
#define REP(i, n) for (int i = 0, _n = (n); i < _n; ++i)
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define PR(a,n) { cerr << #a << " = "; FOR(_,1,n) cerr << a[_] << ' '; cerr << endl; }
#define PR0(a,n) { cerr << #a << " = "; REP(_,n) cerr << a[_] << ' '; cerr << endl; }
#define debug(x) cerr << #x << " = " << x << endl
#define TIME (1.0 * clock() / CLOCKS_PER_SEC)
#define __builtin_popcount __builtin_popcountll
typedef unsigned long long ull;
typedef long long ll;
typedef pair<int, int> pii;
template <class T, class T2> ostream &operator<<(ostream &o, pair<T, T2> p)
{
    o << "(" << p.first << ", " << p.second << ")"; 
    return o;
}
namespace ModInt
{
    const int MOD = 1e9 + 7;
    int add(int x, int y)
    {
        return (x + y) % MOD;
    }
    int sub(int x, int y)
    {
        return (x - y + MOD) % MOD;
    }
    int mul(int x, int y)
    {
        return 1ll * x * y % MOD;
    }
    int pow_mod(int x, int y)
    {
        if (y == 0)
            return 1;
        int t = pow_mod(x, y >> 1);
        if (y % 2 == 0)
            return mul(t, t);
        return mul(x, mul(t, t));
    }
    int div(int x, int y)
    {
        return mul(x, pow_mod(y, MOD - 2));
    }
    int sum_progress(int fi, int len, int d)
    {
        int last = fi + (len - 1) * d;
        return div(mul(add(fi, last), len), 2);  
    }
}

using namespace ModInt;
signed main()
{
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    vector <int> hRow(n + 1, 1), hCol(m + 1, 1);
    while (q--)
    {
        char type;
        int pos, val;
        cin >> type >> pos >> val;
        if (type == 'R')
            hRow[pos] = mul(hRow[pos], val);
        else
            hCol[pos] = mul(hCol[pos], val);
    }
    // PR(hRow, n);
    // PR(hCol, m);
    vector <int> rowGreaterThan1;
    int res = 0;
    for (int i = 1 ; i <= n; ++i)
    {
        if (hRow[i] != 1)
        {
            rowGreaterThan1.push_back(i);
            for (int j = 1; j <= m; ++j)
                res = add(res, mul(hRow[i], mul(hCol[j], (i - 1) * m + j)));
                // cout << mul(hRow[i], mul(hCol[j], (i - 1) * m + j)) << " ";
        }
        // cout << endl;
    }
    // debug(res);
    for (int j = 1; j <= m; ++j)
    {
        res = add(res, mul(hCol[j], sum_progress(j, n, m)));
        for (auto i: rowGreaterThan1)
            res = sub(res, mul(hCol[j], (i - 1) * m + j));
    }
    cout << res;
}

Subtask #1
55.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 348 KB Output is correct
10 Correct 3 ms 348 KB Output is correct
11 Incorrect 338 ms 1680 KB Output isn't correct
12 Execution timed out 1070 ms 4440 KB Time limit exceeded
13 Correct 128 ms 860 KB Output is correct
14 Incorrect 218 ms 5212 KB Output isn't correct
15 Execution timed out 1065 ms 4700 KB Time limit exceeded
16 Execution timed out 1045 ms 8284 KB Time limit exceeded
17 Execution timed out 1068 ms 8532 KB Time limit exceeded
18 Execution timed out 1038 ms 8280 KB Time limit exceeded
19 Execution timed out 1072 ms 8284 KB Time limit exceeded
20 Execution timed out 1022 ms 8280 KB Time limit exceeded