oj.uz

Submission #321131

# Submission time Handle Problem Language Result Execution time Memory
321131 2020-11-11T05:34:42 Z CodeTiger927 Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 29028 KB 
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 = poly();
		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) continue;
				ret.coefs[i + j] += (coefs[i] * b.coefs[j]) % MOD;
				if(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];
 
long long inv(long long a,long long b){
	return 1 < a ? b - inv(b % a,a) * b / a : 1;
}
 
long long inv(long long 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) % 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(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
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 94 ms 25964 KB Output isn't correct
2 Incorrect 108 ms 25964 KB Output isn't correct
3 Incorrect 92 ms 26084 KB Output isn't correct
4 Execution timed out 4010 ms 28460 KB Time limit exceeded
5 Execution timed out 4054 ms 29028 KB Time limit exceeded
6 Execution timed out 4027 ms 28924 KB Time limit exceeded
7 Execution timed out 4014 ms 28408 KB Time limit exceeded
8 Execution timed out 4043 ms 28664 KB Time limit exceeded
9 Execution timed out 4027 ms 28744 KB Time limit exceeded
10 Execution timed out 4100 ms 28764 KB Time limit exceeded