Submission #98659

#	Time	Username	Problem	Language	Result	Execution time	Memory
98659		Tieuphong	Relativnost (COCI15_relativnost)	C++11	140 / 140	3069 ms	25872 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;

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 cong(int a, int b) {int res = a+b; if (res > MOD) return res-MOD; else return res;}

struct IT
{
    int t[N<<2][C], total[N<<2];

    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];
            total[id] = cong(a[x], b[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)
                if (i+j < c) add(t[id][i+j], (1ll*t[id*2][i] * t[id*2+1][j]) % MOD);// = (1ll*t[id][i+j] + ((1ll*t[id*2][i] * t[id*2+1][j]) % MOD)) % MOD;
        total[id] = (1ll*total[id*2] * total[id*2+1]) % MOD;
    }

    int Get()
    {
        int res = total[1];
        FOR(i, 0, c-1)
             res = (1ll*res - t[1][i] + 1ll*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], a[i] %= MOD;
    FOR(i, 1, n) cin >> b[i], b[i] %= MOD;
    FOR(i, 1, n) Tree.Upd(1, n, 1, i);
    cin >> q;
    while (q--)
    {
        int pos, x, y;
        cin >> pos >> x >> y;
        a[pos] = x;
        b[pos] = y;
        Tree.Upd(1, n, 1, pos);
        cout << Tree.Get() << '\n';
    }
    return 0;
}

• Subtask 1: 140 / 140