oj.uz

답안 #98746

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98746 2019-02-25T14:45:56 Z popopo3124 Relativnost (COCI15_relativnost) C++14
140 / 140
 3283 ms 25572 KB 
#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.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 512 KB Output is correct
2 Correct 12 ms 512 KB Output is correct
3 Correct 25 ms 512 KB Output is correct
4 Correct 448 ms 13308 KB Output is correct
5 Correct 1376 ms 25572 KB Output is correct
6 Correct 2165 ms 25476 KB Output is correct
7 Correct 926 ms 13264 KB Output is correct
8 Correct 462 ms 25244 KB Output is correct
9 Correct 858 ms 25308 KB Output is correct
10 Correct 3283 ms 25512 KB Output is correct