oj.uz

Submission #1032203

# Submission time Handle Problem Language Result Execution time Memory
1032203 2024-07-23T13:08:25 Z giorgitsibadze Relativnost (COCI15_relativnost) C++14
140 / 140
 2956 ms 24912 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
// #define int long long
#define ll long long
#define pb push_back
#define popb pop_back
#define pii pair<int, int>
#define pll pair<ll, ll>
using namespace std;

const int mod = 1e4 + 7;
const int inf = 1e15;

int n, c;
int a[100001], b[100001];
int t[400001][21];

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

void build(int v, int tl, int tr) {
    if(tl == tr) {
        (t[v][1] = a[tl]) %= mod;
        (t[v][0] = b[tl]) %= mod;
        return;
    }
    int tm = (tl + tr) / 2;
    build(2 * v, tl, tm);
    build(2 * v + 1, tm + 1, tr);
    merge(v);
}

void update(int v, int tl, int tr, int x) {
    if(tl == tr) {
        (t[v][1] = a[x]) %= mod;
        (t[v][0] = b[x]) %= mod;
        return;
    }
    int tm = (tl + tr) / 2;
    if(x <= tm) {
        update(2 * v, tl, tm, x);
    } else update(2 * v + 1, tm + 1, tr, x);
    for(int i = 0; i <= c; i++) t[v][i] = 0;
    merge(v);
}

void solve() {
    cin >> n >> c;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
    } for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    build(1, 1, n);
    int q;
    cin >> q;
    while(q--) {
        int p;
        cin >> p >> a[p] >> b[p];
        update(1, 1, n, p);
        cout << t[1][c] << '\n';
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    
    int t = 1;
    //cin >> t;
    while(t--) {
        solve();
        cout << '\n';
    }
    return 0;
}

Compilation message

relativnost.cpp:12:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+15' to '2147483647' [-Woverflow]
   12 | const int inf = 1e15;
      |                 ^~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2648 KB Output is correct
2 Correct 11 ms 2652 KB Output is correct
3 Correct 22 ms 2696 KB Output is correct
4 Correct 338 ms 13820 KB Output is correct
5 Correct 1225 ms 24756 KB Output is correct
6 Correct 1858 ms 24912 KB Output is correct
7 Correct 797 ms 13908 KB Output is correct
8 Correct 403 ms 24644 KB Output is correct
9 Correct 708 ms 24912 KB Output is correct
10 Correct 2956 ms 24824 KB Output is correct