Submission #321133

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
321133	2020-11-11T05:41:38 Z	CodeTiger927	Relativnost (COCI15_relativnost)	C++14	112 / 140	4000 ms	24320 KB

relativnost

using namespace std;
 
#include <iostream>
#include <cstring>
 
#define MAXN 100005
#define MOD 10007
#define MAXC 21
 
 
// 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) {
			if(coefs[i] == 0) continue;
			for(int j = 0;j < MAXC;++j) {
				if(i + j < MAXC) ret.coefs[i + j] += coefs[i] * b.coefs[j] % MOD;
				if(i + j < MAXC && ret.coefs[i + j] >= MOD) ret.coefs[i + 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) {
		long long cur;
		cin >> cur;
		cur %= MOD;
		arrA[i] = cur;
	}
	for(int i = 0;i < N;++i) {
		long long cur;
		cin >> cur;
		cur %= MOD;
		arrB[i] = cur;
		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;
		long long b,c;
		cin >> a >> b >> c;
		a--;
		prod = (prod * inv(arrA[a] + arrB[a]) % MOD) * (b + c) % MOD;
		arrA[a] = b;
		arrB[a] = c;
		update(a,poly(c,b));
		// cout << prod << " " << getPoly(0,N - 1).getSum(C - 1) << endl;
		cout << ((prod - getPoly(0,N - 1).getSum(C - 1) + MOD) % MOD) << endl;
	}
}

Subtask #1

112.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	72 ms	21868 KB	Output is correct
2	Correct	86 ms	21868 KB	Output is correct
3	Correct	69 ms	21868 KB	Output is correct
4	Correct	2986 ms	23632 KB	Output is correct
5	Correct	3964 ms	24320 KB	Output is correct
6	Correct	3472 ms	24064 KB	Output is correct
7	Correct	2971 ms	23352 KB	Output is correct
8	Correct	3173 ms	23268 KB	Output is correct
9	Execution timed out	4054 ms	24176 KB	Time limit exceeded
10	Execution timed out	4011 ms	24260 KB	Time limit exceeded