oj.uz

Submission #98565

# Submission time Handle Problem Language Result Execution time Memory
98565 2019-02-24T10:48:34 Z polyfish Relativnost (COCI15_relativnost) C++14
98 / 140
 2666 ms 33792 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 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.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 640 KB Output is correct
2 Correct 19 ms 640 KB Output is correct
3 Correct 40 ms 768 KB Output is correct
4 Correct 778 ms 18720 KB Output is correct
5 Runtime error 2666 ms 33792 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 71 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 1802 ms 25692 KB Output is correct
8 Correct 1114 ms 30072 KB Output is correct
9 Correct 1539 ms 26232 KB Output is correct
10 Runtime error 69 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)