Submission #1032173

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1032173	2024-07-23T12:48:02 Z	giorgitsibadze	Relativnost (COCI15_relativnost)	C++14	0 / 140	2424 ms	50772 KB

relativnost

#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++) t[v][i] = 0;
    for(int i = 0; i <= c; i++) {
        for(int j = 0; j <= c; j++) {
            (t[v][min(i + j, c)] += t[2 * v][i] * t[2 * v + 1][j]) %= 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, int val1, int val2) {
    if(tl == tr) {
        t[v][1] = val1 % mod;
        t[v][0] = val2 % mod;
        return;
    }
    int tm = (tl + tr) / 2;
    if(x <= tm) {
        update(2 * v, tl, tm, x, val1, val2);
    }
    else update(2 * v + 1, tm + 1, tr, x, val1, val2);
    merge(v);
}


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

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	5 ms	4700 KB	Output isn't correct
2	Incorrect	9 ms	4748 KB	Output isn't correct
3	Incorrect	17 ms	4752 KB	Output isn't correct
4	Incorrect	247 ms	27728 KB	Output isn't correct
5	Runtime error	864 ms	50772 KB	Memory limit exceeded
6	Runtime error	1503 ms	50512 KB	Memory limit exceeded
7	Incorrect	616 ms	28056 KB	Output isn't correct
8	Runtime error	345 ms	50004 KB	Memory limit exceeded
9	Runtime error	636 ms	50772 KB	Memory limit exceeded
10	Runtime error	2424 ms	48976 KB	Memory limit exceeded