oj.uz

Submission #98575

# Submission time Handle Problem Language Result Execution time Memory
98575 2019-02-24T14:24:33 Z tieunhi Relativnost (COCI15_relativnost) C++14
140 / 140
 2702 ms 26916 KB 
#include <bits/stdc++.h>
#define FOR(i, u, v) for (int i = u; i <= v; i++)
#define FORD(i, v, u) for (int i = v; i >= u; i--)
#define pii pair<int, int>
#define mp make_pair
#define F first
#define S second
#define PB push_back
#define N 100005
#define mod 10007
#define ll long long
#define mid (r + l)/2
using namespace std;

void inline add(int &A, int B) {A += B; if (A >= mod) A -= mod;}
void inline sub(int &A, int B) {A -= B; if (A < 0) A += mod;}
int inline mul(int A, int B) {return (1ll*A*B) % mod;}

int n, C, a[N], b[N];

struct IntervalTree
{
    int t[N << 2][20];
    int total[N << 2];

    void Merge(int id)
    {
        FOR(i, 0, C) t[id][i] = 0;
        FOR(i, 0, C)
            FOR(j, 0, C)
                if (i + j <= C)
                    add(t[id][i+j], mul(t[id*2][i], t[id*2+1][j]));
        total[id] = mul(total[id*2], total[id*2+1]);
    }
    void update(int l, int r, int id, int x)
    {
        if (l == r)
        {
            t[id][0] = b[l];
            t[id][1] = a[l];
            total[id] = (a[l] + b[l]) % mod;
            return;
        }
        if (x <= mid) update(l, mid, id*2, x);
        else update(mid+1, r, id*2+1, x);
        Merge(id);
    }
    int getAns()
    {
        int res = total[1];
        FOR(i, 0, C) sub(res, t[1][i]);
        return res;
    }
}t;


int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    //freopen("INP.TXT", "r", stdin);
    cin >> n >> C; C--;
    FOR(i, 1, n) cin >> a[i], a[i] %= mod;
    FOR(i, 1, n) cin >> b[i], b[i] %= mod;
    FOR(i, 1, n) t.update(1, n, 1, i);

    int numQ; cin >> numQ;
    while (numQ--)
    {
        int pos, x, y; cin >> pos >> x >> y;
        a[pos] = x % mod;
        b[pos] = y % mod;
        t.update(1, n, 1, pos);
        cout <<t.getAns()<<'\n';
    }
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 512 KB Output is correct
2 Correct 11 ms 512 KB Output is correct
3 Correct 18 ms 512 KB Output is correct
4 Correct 408 ms 11896 KB Output is correct
5 Correct 1401 ms 24276 KB Output is correct
6 Correct 2050 ms 26552 KB Output is correct
7 Correct 716 ms 11848 KB Output is correct
8 Correct 463 ms 22916 KB Output is correct
9 Correct 741 ms 23032 KB Output is correct
10 Correct 2702 ms 26916 KB Output is correct