oj.uz

Submission #321123

# Submission time Handle Problem Language Result Execution time Memory
321123 2020-11-11T04:50:42 Z CodeTiger927 Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 56728 KB 
using namespace std;

#include <iostream>
#include <cstring>

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


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

	poly(long long a,long long 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;
	}

	long long getSum(int n) {
		long long 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;
long long 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() {
	long long 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 Runtime error 110 ms 51684 KB Memory limit exceeded
2 Runtime error 121 ms 51812 KB Memory limit exceeded
3 Runtime error 104 ms 51684 KB Memory limit exceeded
4 Execution timed out 4056 ms 55564 KB Time limit exceeded
5 Execution timed out 4051 ms 56404 KB Time limit exceeded
6 Execution timed out 4067 ms 56616 KB Time limit exceeded
7 Execution timed out 4040 ms 55700 KB Time limit exceeded
8 Execution timed out 4030 ms 56728 KB Time limit exceeded
9 Execution timed out 4059 ms 56184 KB Time limit exceeded
10 Execution timed out 4037 ms 56104 KB Time limit exceeded