Submission #321124

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321124	2020-11-11T04:51:58 Z	CodeTiger927	Relativnost (COCI15_relativnost)	C++14	0 / 140	4000 ms	27280 KB

relativnost

using namespace std;

#include <iostream>
#include <cstring>

#define MAXN 100005
#define MOD 10007
#define MAXC 25


// Polynomial template
struct poly {
	int coefs[MAXC];
	poly() {
		memset(coefs,0,sizeof(coefs));
		coefs[0] = 1;
	}

	poly(int a,int b) {
		memset(coefs,0,sizeof(coefs));
		coefs[0] = a % MOD;
		coefs[1] = b % MOD;
	}

	poly operator *(const poly& b) {
		poly ret;
		ret.coefs[0] = 0;
		for(int i = 0;i < MAXC;++i) {
			for(int j = 0;j < MAXC;++j) {
				if(i + j < MAXC) ret.coefs[i + j] += coefs[i] * b.coefs[j] % MOD;
			}
		}
		return ret;
	}

	int getSum(int n) {
		int res = 0;
		for(int i = 0;i <= n;++i) {
			res += coefs[i];
			if(res > MOD) res -= MOD;
		}
		return res;
	}
};

poly st[262144];

void update(int x,poly v,int l,int r,int p) {
	if(l > x || r < x) return;
	if(l == r) {
		st[p] = v;
		return;
	}
	int m = (l + r) / 2;
	update(x,v,l,m,2 * p + 1);
	update(x,v,m + 1,r,2 * p + 2);
	st[p] = st[2 * p + 1] * st[2 * p + 2];
	return;
}

void update(int x,poly v) {
	update(x,v,0,MAXN,0);
}

poly getPoly(int a,int b,int l,int r,int p) {
	if(l > b || r < a) return poly();
	if(l >= a && r <= b) return st[p];
	int m = (l + r) / 2;
	return getPoly(a,b,l,m,2 * p + 1) * getPoly(a,b,m + 1,r,2 * p + 2);
}

poly getPoly(int a,int b) {
	return getPoly(a,b,0,MAXN,0);
}

int N,C,Q;
int arrA[MAXN],arrB[MAXN];

int inv(int a,int b){
	return 1 < a ? b - inv(b % a,a) * b / a : 1;
}

int inv(int a) {
	return inv(a,MOD);
}

int main() {
	int prod = 1;
	for(int i = 0;i < 262144;++i) {
		st[i] = poly();
	}
	cin >> N >> C;
	for(int i = 0;i < N;++i) {
		cin >> arrA[i];
	}
	for(int i = 0;i < N;++i) {
		cin >> arrB[i];
		update(i,poly(arrB[i],arrA[i]));
		prod = (prod * (arrA[i] + arrB[i])) % MOD;
	}
	cin >> Q;
	for(int i = 0;i < Q;++i) {
		int a,b,c;
		cin >> a >> b >> c;
		a--;
		prod = (prod * inv(arrA[a] + arrB[a]) % MOD) * (b + c) % MOD;
		update(a,poly(b,c));
		// cout << prod << " " << getPoly(0,N - 1).getSum(0) << endl;
		cout << ((prod - getPoly(0,N - 1).getSum(C - 1) + MOD) % MOD) << endl;
	}

}

Subtask #1

0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	93 ms	25964 KB	Output isn't correct
2	Incorrect	103 ms	25964 KB	Output isn't correct
3	Incorrect	92 ms	25964 KB	Output isn't correct
4	Execution timed out	4038 ms	26952 KB	Time limit exceeded
5	Execution timed out	4051 ms	27280 KB	Time limit exceeded
6	Execution timed out	4049 ms	27276 KB	Time limit exceeded
7	Execution timed out	4061 ms	26932 KB	Time limit exceeded
8	Execution timed out	4003 ms	27156 KB	Time limit exceeded
9	Execution timed out	4010 ms	27268 KB	Time limit exceeded
10	Execution timed out	4048 ms	27232 KB	Time limit exceeded