Submission #98746

#	Time	Username	Problem	Language	Result	Execution time	Memory
98746		popopo3124	Relativnost (COCI15_relativnost)	C++14	140 / 140	3283 ms	25572 KiB

relativnost

#include<bits/stdc++.h>
using namespace std;
typedef int lli;
const lli N=100009, K=21, mod=10007;
lli n, c, a[N], b[N];
lli low[4*N], high[4*N], leaf[N];
struct T
{
	lli x[K]={};
};
T node[4*N];
lli Next()
{
    register char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        ch=getchar();
    }
    lli l=0;
    while(ch>='0'&&ch<='9')
    {
        l=l*10+ch-'0';
        ch=getchar();
    }
    return l;
}
void Combine(lli v)
{
    lli p=v*2, q=v*2+1;
    for(int i=0;i<=c;i++)
    {
        node[v].x[i]=0;
    }
	for(int i=0;i<=c;i++)
	{
		for(int j=0;j<=c;j++)
		{
			if(i+j<c)
			{
				node[v].x[i+j]=(node[v].x[i+j]+node[p].x[i]*node[q].x[j])%mod;
			}
			else
			{
				node[v].x[c]=(node[v].x[c]+node[p].x[i]*node[q].x[j])%mod;
			}
		}
	}
}
void Built(lli v, lli l, lli h)
{
	low[v]=l;
	high[v]=h;
	if(l==h)
	{
		leaf[l]=v;
		node[v].x[0]=b[l]%mod;
		node[v].x[1]=a[l]%mod;
	}
	else
	{
		lli m=(l+h)/2;
		Built(v*2, l, m);
		Built(v*2+1, m+1, h);
		Combine(v);
	}
}
void Update(lli x, lli a, lli b)
{
	lli v=leaf[x];
	node[v].x[0]=b%mod;
	node[v].x[1]=a%mod;
	v=v/2;
	while(v)
	{
		Combine(v);
		v=v/2;
	}
}
void Inp()
{
	n=Next();
	c=Next();
	for(int i=1;i<=n;i++)
	{
		a[i]=Next();
	}
	for(int i=1;i<=n;i++)
	{
		b[i]=Next();
	}
	Built(1, 1, n);
}
void Solve()
{
	lli q;
	q=Next();
	for(int i=1;i<=q;i++)
	{
		lli x, a, b;
		x=Next();
		a=Next();
		b=Next();
		Update(x, a, b);
		cout<<node[1].x[c]<<'\n';
	}
}
int main()
{
	//freopen("test.inp","r",stdin);freopen("out.out","w",stdout);
	Inp();
	Solve();
}

• Subtask 1: 140 / 140