Submission #374210

#	Time	Username	Problem	Language	Result	Execution time	Memory
374210		Nimbostratus	Relativnost (COCI15_relativnost)	C++17	140 / 140	1470 ms	30828 KiB

relativnost

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define clean(a,s) memset((a),0,sizeof((a)[0])*(s))
#define all(x) (x).begin() , (x).end()
#define fi first
#define se second
#define int long long
using pii = pair<int,int>;
using ll = long long;
const int maxn = 2e5+5;
const int inf = 2e9;
const int mod = 1e4+7;

int n,c,q,a[maxn],b[maxn];
vector<int> t[4*maxn];

void build(int vi,int vl,int vr) {
	if(vl == vr) {
		t[vi].resize(min(c,2ll));
		t[vi][0] = b[vl]%mod;
		if(t[vi].size() > 1) t[vi][1] = a[vl]%mod;
		return;
	}
	int mid = (vl+vr)/2;
	int sz = min(c,vr-vl+2);
	int lsz = min(c,mid-vl+2);
	int rsz = min(c,vr-mid+1);
	build(2*vi,vl,mid);
	build(2*vi+1,mid+1,vr);
	t[vi].resize(sz);
	for(int i=0;i<lsz;i++)
		for(int j=0;j<rsz;j++) {
			if(i+j >= sz) break;
			t[vi][i+j] += t[2*vi][i]*t[2*vi+1][j]%mod;
			t[vi][i+j] %= mod;
		}
}

void update(int vi,int vl,int vr,int pos) {
	if(vl == vr && vl == pos) {
		t[vi][0] = b[vl]%mod;
		if(t[vi].size() > 1) t[vi][1] = a[vl]%mod;
		return;
	}
	int mid = (vl+vr)/2;
	if(pos <= mid) update(2*vi,vl,mid,pos);
	else update(2*vi+1,mid+1,vr,pos);
	int sz = min(c,vr-vl+2);
	int lsz = min(c,mid-vl+2);
	int rsz = min(c,vr-mid+1);
	t[vi].assign(sz,0);
	for(int i=0;i<lsz;i++)
		for(int j=0;j<rsz;j++) {
			if(i+j >= sz) break;
			t[vi][i+j] += t[2*vi][i]*t[2*vi+1][j]%mod;
			t[vi][i+j] %= mod;
		}	
}

int exp(int p,int k) {
	int ret = 1;
	while(k) {
		if(k&1) ret = (ret*p)%mod;
		p = (p*p)%mod;
		k >>= 1;
	}
	return ret;
}


int32_t main () {
	//freopen("in","r",stdin); freopen("out","w",stdout);
	ios_base::sync_with_stdio(0); cout.tie(0); cin.tie(0);
	cin >> n >> c;
	for(int i=1;i<=n;i++) cin >> a[i];
	for(int i=1;i<=n;i++) cin >> b[i];
	build(1,1,n);
	int mul = 1;
	for(int i=1;i<=n;i++) mul = mul*(a[i]+b[i])%mod;
	cin >> q;
	while(q--) {
		int p,aa,bb;
		cin >> p >> aa >> bb;
		mul *= (aa%mod+bb%mod)%mod;
		mul %= mod;
		mul *= exp(a[p]+b[p],mod-2);
		mul %= mod;
		a[p] = aa , b[p] = bb;
		update(1,1,n,p);
		int ans = 0;
		for(int i=0;i<t[1].size();i++) {
			//cout << t[1][i] << endl;
			ans = (ans+t[1][i])%mod;
		}
		ans = (mul-ans+2*mod)%mod;
		cout << ans << endl;
	}
}	
	

Compilation message (stderr)

relativnost.cpp: In function 'int32_t main()':
relativnost.cpp:94:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |   for(int i=0;i<t[1].size();i++) {
      |               ~^~~~~~~~~~~~

• Subtask 1: 140 / 140