oj.uz

Submission #39428

# Submission time Handle Problem Language Result Execution time Memory
39428 2018-01-15T06:12:27 Z adamczh1 Relativnost (COCI15_relativnost) C++14
140 / 140
 2763 ms 18460 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

#define SIZE(x) (int)(x).size()
#define ALL(x) (x).begin(),(x).end()
#define ff first
#define ss second

inline ll readi(){
	ll x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}

const int MAXN=1e5+5;
const int MOD=10007;

int N,C,Q;
int inv[MOD];
int a[MAXN];
int b[MAXN];
int tree[20][2*MAXN];
inline void pull(int x){
	for(int i=0;i<C;i++){
		tree[i][x]=0;
		for(int j=0;j<=i;j++)
			tree[i][x]=(tree[i][x]+tree[j][x<<1]*tree[i-j][x<<1|1])%MOD;
	}
}
inline void update(int p){
	int x=p+MAXN;
	tree[0][x]=b[p]%MOD;
	tree[1][x]=a[p]%MOD;
	for(x>>=1;x>0;x>>=1) pull(x);
}

int main(){
	inv[1]=1;
	for(int i=2;i<MOD;i++) inv[i]=(MOD-(MOD/i)*inv[MOD%i]%MOD)%MOD;
	N=readi(),C=readi();
	int tot=1;
	for(int i=1;i<=N;i++) a[i]=readi();
	for(int i=1;i<=N;i++) b[i]=readi(), tot=tot*((a[i]+b[i])%MOD)%MOD;
	for(int i=1;i<2*MAXN;i++)tree[0][i]=1;
	for(int i=1;i<=N;i++) update(i);
	Q=readi();
	while(Q--){
		int P=readi();
		tot=tot*inv[(a[P]+b[P])%MOD]%MOD;
		a[P]=readi(),b[P]=readi();
		tot=tot*((a[P]+b[P])%MOD)%MOD;
		update(P);
		int res=tot;
		for(int i=0;i<C;i++)res=(res-tree[i][1])%MOD;
		res=(res+MOD)%MOD;
		printf("%d\n",res);
	}
	return 0;
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 18460 KB Output is correct
2 Correct 9 ms 18460 KB Output is correct
3 Correct 26 ms 18460 KB Output is correct
4 Correct 269 ms 18460 KB Output is correct
5 Correct 1156 ms 18460 KB Output is correct
6 Correct 2106 ms 18460 KB Output is correct
7 Correct 736 ms 18460 KB Output is correct
8 Correct 433 ms 18460 KB Output is correct
9 Correct 653 ms 18460 KB Output is correct
10 Correct 2763 ms 18460 KB Output is correct