oj.uz

Submission #321125

# Submission time Handle Problem Language Result Execution time Memory
321125 2020-11-11T04:53:40 Z CodeTiger927 Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 27356 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;
		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) {
		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,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 97 ms 25964 KB Output isn't correct
2 Incorrect 109 ms 26084 KB Output isn't correct
3 Incorrect 91 ms 25964 KB Output isn't correct
4 Execution timed out 4094 ms 27108 KB Time limit exceeded
5 Execution timed out 4018 ms 27276 KB Time limit exceeded
6 Execution timed out 4010 ms 27248 KB Time limit exceeded
7 Execution timed out 4013 ms 27144 KB Time limit exceeded
8 Execution timed out 4005 ms 27324 KB Time limit exceeded
9 Execution timed out 4030 ms 27224 KB Time limit exceeded
10 Execution timed out 4011 ms 27356 KB Time limit exceeded