oj.uz

Submission #98640

# Submission time Handle Problem Language Result Execution time Memory
98640 2019-02-25T02:26:33 Z polyfish Relativnost (COCI15_relativnost) C++14
42 / 140
 1463 ms 27600 KB 
//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];

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

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 * (ap+bp) % MOD;
        tr.upd(p, ap, bp);

        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
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 9 ms 512 KB Output is correct
3 Correct 15 ms 512 KB Output is correct
4 Incorrect 279 ms 14840 KB Output isn't correct
5 Incorrect 785 ms 27600 KB Output isn't correct
6 Incorrect 1057 ms 26528 KB Output isn't correct
7 Incorrect 481 ms 15012 KB Output isn't correct
8 Incorrect 370 ms 26488 KB Output isn't correct
9 Incorrect 510 ms 26512 KB Output isn't correct
10 Incorrect 1463 ms 26580 KB Output isn't correct