oj.uz

Submission #98685

# Submission time Handle Problem Language Result Execution time Memory
98685 2019-02-25T03:59:55 Z HellAngel Relativnost (COCI15_relativnost) C++14
70 / 140
 931 ms 33792 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int maxn = 1e5 + 7;
const int somod = 10007;
struct Node
{
    int ans[22];
} IT[4 * maxn];

int n, c, a[maxn], b[maxn];

void Add(int &a, int b)
{
    a = (a + b) % somod;
}

Node Merge(const Node &a, const Node &b)
{
    Node gau;
    for(int i = 0; i <= c; i++) gau.ans[i] = 0;
    for(int i = 0; i <= c; i++)
    {
        for(int j = 0; j <= c; j++)
        {
            Add(gau.ans[min(i + j, c)], a.ans[i] * b.ans[j]);
        }
    }
    return gau;
}

void Build(int id, int l, int r)
{
    if(l == r)
    {
        Node gau;
        for(int i = 0; i <= c; i++) gau.ans[i] = 0;
        gau.ans[0] = b[l];
        gau.ans[1] = a[l];
        IT[id] = gau;
        return;
    }
    int mid = l + r >> 1;
    Build(id * 2, l, mid);
    Build(id * 2 + 1, mid + 1, r);
    IT[id] = Merge(IT[id * 2], IT[id * 2 + 1]);
}

void Update(int id, int l, int r, int pos, int va, int vb)
{
    if(l == r)
    {
        IT[id].ans[0] = vb;
        IT[id].ans[1] = va;
        return;
    }
    int mid = l + r >> 1;
    if(pos <= mid) Update(id * 2, l, mid, pos, va, vb);
    else Update(id * 2 + 1, mid + 1, r, pos, va, vb);
    IT[id] = Merge(IT[id * 2], IT[id * 2 + 1]);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("test.inp", "r", stdin);
    //freopen("test.out", "w", stdout);
    cin >> n >> c;
    for(int i = 1; i <= n; i++) cin >> a[i], a[i] %= somod;
    for(int i = 1; i <= n; i++) cin >> b[i], b[i] %= somod;
    Build(1, 1, n);
    int q;
    cin >> q;
    for(int i = 1; i <= q; i++)
    {
        int pos, a, b;
        cin >> pos >> a >> b;
        Update(1, 1, n, pos, a, b);
        cout << IT[1].ans[c] << '\n';
    }
}

Compilation message

relativnost.cpp: In function 'void Build(long long int, long long int, long long int)':
relativnost.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~
relativnost.cpp: In function 'void Update(long long int, long long int, long long int, long long int, long long int, long long int)':
relativnost.cpp:58:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = l + r >> 1;
               ~~^~~

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 768 KB Output is correct
2 Correct 14 ms 768 KB Output is correct
3 Correct 28 ms 768 KB Output is correct
4 Correct 461 ms 24320 KB Output is correct
5 Runtime error 110 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 150 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 931 ms 24276 KB Output is correct
8 Runtime error 77 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 94 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 167 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)