oj.uz

답안 #98744

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98744 2019-02-25T14:44:42 Z popopo3124 Relativnost (COCI15_relativnost) C++14
70 / 140
 500 ms 33792 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long 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]);
			}
			else
			{
				node[v].x[c]=(node[v].x[c]+node[p].x[i]*node[q].x[j]);
			}
		}
	}
	for(int i=0;i<=c;i++)
    {
        node[v].x[i]%=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
70.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 768 KB Output is correct
2 Correct 7 ms 768 KB Output is correct
3 Correct 13 ms 768 KB Output is correct
4 Correct 285 ms 26104 KB Output is correct
5 Runtime error 89 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
6 Runtime error 93 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
7 Correct 500 ms 26420 KB Output is correct
8 Runtime error 67 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Runtime error 64 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)
10 Runtime error 94 ms 33792 KB Execution killed with signal 9 (could be triggered by violating memory limits)