oj.uz

Submission #246310

# Submission time Handle Problem Language Result Execution time Memory
246310 2020-07-08T15:50:53 Z bibabas Relativnost (COCI15_relativnost) C++14
70 / 140
 4000 ms 45856 KB 
#include <bits/stdc++.h>
 
#define int long long
#define ull unsigned int
#define vi vector<int>
#define vvi vector<vi>
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ld long double
#define pii pair<int, int>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
 
using namespace std;
 
const int INF = (int)2e9;
const int inf = (int)2e18;
const ld eps = (ld)1e-8;
const int mod = (int)10007;
const int MAXN = (int)1e4 + 1;
const int MAXC = (int)1e6 + 1;
const int MAXE = (int)1000;
const int MAXLOG = 21;
const int maxlen = (int)1e5;
const int asci = (int)256;
const int block = 480;
const ld PI = acos(-1);
const ld e = 2.7182818284;
 
/*#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<
pii,
null_type,
less<pii>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;*/
 
template <class T>
istream& operator >>(istream &in, vector<T> &arr){
    for (T &cnt : arr) {
        in >> cnt;
    }
    return in;
};

int c = 0;
int t[400000][21];

void merge(int v) {
    for (int i = 0; i <= 20; ++i) t[v][i] = 0;
    for (int i = 0; i <= 20; ++i) {
        for (int j = 0; j <= 20; ++j) {
            t[v][min(c, i + j)] += (t[2 * v][i] * t[2 * v + 1][j]) % mod;
            t[v][min(c, i + j)] %= mod;
        }
    }
}

void build(int v, int tl, int tr, vector<pii> &a) {
    if (tl + 1 == tr) {
        t[v][1] = a[tl].first, t[v][0] = a[tl].second;
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm, a);
    build(2 * v + 1, tm, tr, a);
    merge(v);
}

void upd(int v, int tl, int tr, int pos, pii val) {
    if (tl + 1 == tr) {
        t[v][1] = val.first, t[v][0] = val.second;
        return;
    }
    int tm = (tl + tr) / 2;
    if (pos < tm) upd(2 * v, tl, tm, pos, val);
    else upd(2 * v + 1, tm, tr, pos, val);
    merge(v);
}

void solve() {
    int n; cin >> n >> c;
    vector<pii> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first;
    }
    for (int i = 0; i < n; ++i) {
        cin >> a[i].second;
    }
    build(1, 0, n, a);
    int q; cin >> q;
    while (q--) {
        int pos; pii val; cin >> pos >> val.first >> val.second;
        pos--;
        upd(1, 0, n, pos, val);
        cout << t[1][c] << "\n";
    }
}

signed main() {
    srand(time(0));
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#endif
    cout.precision(30);
    
    solve();
 
    return 0;
}

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 768 KB Output is correct
2 Correct 51 ms 768 KB Output is correct
3 Correct 34 ms 760 KB Output is correct
4 Correct 3455 ms 23504 KB Output is correct
5 Execution timed out 4049 ms 45664 KB Time limit exceeded
6 Runtime error 3076 ms 45588 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Correct 3080 ms 23740 KB Output is correct
8 Runtime error 3133 ms 45856 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Execution timed out 4051 ms 45608 KB Time limit exceeded
10 Runtime error 3811 ms 41560 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)