Submission #98642

#	Time	Username	Problem	Language	Result	Execution time	Memory
98642		polyfish	Relativnost (COCI15_relativnost)	C++14	140 / 140	1379 ms	24232 KiB

relativnost

//Pantyhose(black) + glasses = infinity

#include <bits/stdc++.h>
using namespace std;

#define debug(x) cerr << #x << " = " << x << '\n';
#define BP() cerr << "OK!\n";
#define PR(A, n) {cerr << #A << " = "; for (int _=1; _<=n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; for (int _=0; _<n; ++_) cerr << A[_] << ' '; cerr << '\n';}
#define FILE_NAME "data"

const int MAX_N = 100002;
const int INF = 1e9;
const int MAX_C = 22;
const int MOD = 10007;

class segmentTree {
public:

    int n, C;
    int st[MAX_N*4][MAX_C];

    void init(int _n, int _C) {
        n = _n;
        C = _C;
    }

    void upd(int pos, int a, int b, int l, int r, int idx) {
        if (pos<l || pos>r)
            return;

        if (l==r) {
            st[idx][0] = b;
            st[idx][1] = a;
            return;
        }

        int mid = (l + r) / 2;
        upd(pos, a, b, l, mid, idx*2);
        upd(pos, a, b, mid+1, r, idx*2+1);

        for (int i=0; i<=C; ++i)
            st[idx][i] = 0;

        for (int i=0; i<C; ++i) {
            for (int j=0; i+j<C; ++j) {
                st[idx][i+j] = st[idx][i+j] + st[idx*2][i] * st[idx*2+1][j];
                if (st[idx][i+j]>INF)
                    st[idx][i+j] %= MOD;
            }
        }

        for (int i=0; i<C; ++i)
            st[idx][i] %= MOD;

//        debug(st[1][C]);
    }

    void upd(int pos, int a, int b) {
        upd(pos, a, b, 1, n, 1);
    }

    int get() {
        int res = 0;

        for (int i=0; i<C; ++i)
            res = (res + st[1][i]) % MOD;

        return res;
    }

};

int n, C, a[MAX_N], b[MAX_N];
segmentTree tr;

void readInput() {
    cin >> n >> C;

    for (int i=1; i<=n; ++i) {
        cin >> a[i];
        a[i] %= MOD;
    }

    for (int i=1; i<=n; ++i) {
        cin >> b[i];
        b[i] %= MOD;
    }
}

int pw(int n, int k) {
    if (k==0)
        return 1;
    int tmp = pw(n, k/2);
    if (k%2)
        return tmp * tmp % MOD * n % MOD;
    return tmp * tmp % MOD;
}

void solve() {
    tr.init(n, C);
    int tmp = 1;

    for (int i=1; i<=n; ++i) {
        tr.upd(i, a[i], b[i]);
        tmp = tmp * (a[i] + b[i]) % MOD;
    }

    int nQueries;
    cin >> nQueries;

    while (nQueries--) {
        int p, ap, bp;
        cin >> p >> ap >> bp;

        tmp = tmp * pw(a[p]+b[p], MOD-2);
        a[p] = ap % MOD;
        b[p] = bp % MOD;
        tmp = tmp * (a[p]+b[p]) % MOD;
        tr.upd(p, a[p], b[p]);

        cout << (tmp - tr.get() + MOD) % MOD << '\n';
    }

}

int main() {
	#ifdef GLASSES_GIRL
		freopen(FILE_NAME".in", "r", stdin);
		//freopen(FILE_NAME".out", "w", stdout);
	#endif
	ios::sync_with_stdio(0); cin.tie(0);
	readInput();
    solve();
}

• Subtask 1: 140 / 140