Submission #98641

#	Time	Username	Problem	Language	Result	Execution time	Memory
98641		Tieuphong	Relativnost (COCI15_relativnost)	C++11	0 / 140	963 ms	33792 KiB

relativnost

/***************************************************************************/
/**********************  LANG TU HAO HOA  **********************************/
/***************************************************************************/
#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define FORD(i, a, b) for (int i = (a); i >= (b); --i)
#define pii pair<int, int>
#define sz(x) ((int) x.size())
#define PB push_back
#define PF push_front
#define MP make_pair
#define ll long long
#define F first
#define S second
#define maxc 1000000007
#define MOD 10007
#define base 107
#define eps 1e-6
#define pi acos(-1)
#define N 100005
#define C 22
#define task ""
#define remain(x) ((x > MOD) ? (x - MOD) : x)

using namespace std;

int n, c, a[N], b[N], q;

ll total;

struct IT
{
    ll t[N<<2][2*C];

    void Upd(int l, int r, int id, int x)
    {
        if (l > x || r < x) return;
        if (l == r)
        {
            t[id][0] = b[x];
            t[id][1] = a[x];
            return;
        }
        int mid = (l + r) >> 1;
        Upd(l, mid, id*2, x);
        Upd(mid+1, r, id*2+1, x);
        FOR(i, 0, c-1) t[id][i] = 0;
        FOR(i, 0, c-1)
            FOR(j, 0, c-1)
                t[id][i+j] += (t[id*2][i] * t[id*2+1][j]) % MOD;
    }

    ll Get()
    {
        ll res = total;
        FOR(i, 0, c-1)
             res = (res - t[1][i] + 1ll*MOD*MOD) % MOD;
        return res;
    }
} Tree;

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    //freopen(task".inp", "r", stdin);
    //freopen(task".out", "w", stdout);
    cin >> n >> c;
    FOR(i, 1, n) cin >> a[i];
    FOR(i, 1, n) cin >> b[i];
    total = 1;
    FOR(i, 1, n)
    {
        Tree.Upd(1, n, 1, i);
        total = (total * (a[i]+b[i])) % MOD;
    }
    cin >> q;
    while (q--)
    {
        int pos, x, y;
        cin >> pos >> x >> y;
        total = (total*(x+y)/(a[pos]+b[pos])) % MOD;
        a[pos] = x;
        b[pos] = y;
        Tree.Upd(1, n, 1, pos);
        cout << Tree.Get() << '\n';
    }
    return 0;
}

• Subtask 1: 0 / 140