Submission #98565

#	Time	Username	Problem	Language	Result	Execution time	Memory
98565		polyfish	Relativnost (COCI15_relativnost)	C++14	98 / 140	2666 ms	33792 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 MOD = 10007;

class segmentTree {
public:

    int n, C;
    vector<vector<int> > st;

    segmentTree(int n, int C): n(n), C(C) {
        st.resize(4*n);
        for (int i=0; i<4*n; ++i)
            st[i].resize(C+1);
    }

    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 % MOD;
            st[idx][1] = a % MOD;
            return;
        }

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

//        debug(st[2][0]);
//        debug(st[2][1]);
//        debug(st[2][2]);
//
//        debug(st[3][0]);
//        debug(st[3][1]);
//        debug(st[3][2]);

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

        for (int i=0; i<=C; ++i) {
            for (int j=0; j<=C; ++j) {
//                debug(st[idx*2][i]);
//                debug(st[idx*2+1][j]);
//                debug(i+j);
                st[idx][min(C, i+j)] = (st[idx][min(C, i+j)] + st[idx*2][i] * st[idx*2+1][j]) % MOD;
//                debug(st[idx][2]);
            }
        }

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

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

    int get() {
        return st[1][C];
    }

};

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

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];
}

void solve() {
    segmentTree tr(n, C);

    for (int i=1; i<=n; ++i)
        tr.upd(i, a[i], b[i]);

    int nQueries;
    cin >> nQueries;

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

        tr.upd(p, ap, bp);

        cout << tr.get() << '\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: 98 / 140