oj.uz

Submission #246307

# Submission time Handle Problem Language Result Execution time Memory
246307 2020-07-08T15:41:23 Z bibabas Relativnost (COCI15_relativnost) C++14
70 / 140
 4000 ms 49232 KB 
#include <bits/stdc++.h>
 
#define ll long long
#define ull unsigned ll
#define vi vector<ll>
#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<ll, ll>
#define mt make_tuple
#define mn(a, b) a = min(a, b)
#define mx(a, b) a = max(a, b)
 
using namespace std;
 
const ll INF = (ll)2e9;
const ll inf = (ll)2e18;
const ld eps = (ld)1e-8;
const ll mod = (ll)10007;
const ll MAXN = (ll)1e4 + 1;
const ll MAXC = (ll)1e6 + 1;
const ll MAXE = (ll)1000;
const ll MAXLOG = 21;
const ll maxlen = (ll)1e5;
const ll asci = (ll)256;
const ll 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;
};

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

void merge(ll v) {
    for (ll i = 0; i <= 20; ++i) t[v][i] = 0;
    for (ll i = 0; i <= 20; ++i) {
        for (ll 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(ll v, ll tl, ll tr, vector<pii> &a) {
    if (tl + 1 == tr) {
        t[v][1] = a[tl].first, t[v][0] = a[tl].second;
        return;
    }
    ll tm = (tl + tr) / 2;
    build(2 * v, tl, tm, a);
    build(2 * v + 1, tm, tr, a);
    merge(v);
}

void upd(ll v, ll tl, ll tr, ll pos, pii val) {
    if (tl + 1 == tr) {
        t[v][1] = val.first, t[v][0] = val.second;
        return;
    }
    ll 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() {
    ll 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);
    ll q; cin >> q;
    while (q--) {
        ll pos; pii val; cin >> pos >> val.first >> val.second;
        pos--;
        upd(1, 0, n, pos, val);
        cout << t[1][c] << "\n";
    }
}

int 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 44 ms 768 KB Output is correct
2 Correct 56 ms 888 KB Output is correct
3 Correct 35 ms 768 KB Output is correct
4 Correct 3441 ms 25728 KB Output is correct
5 Runtime error 3986 ms 49232 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 3058 ms 48860 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Correct 3067 ms 26260 KB Output is correct
8 Runtime error 3181 ms 48516 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Execution timed out 4078 ms 48680 KB Time limit exceeded
10 Runtime error 3709 ms 44812 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)