oj.uz

답안 #217205

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
217205 2020-03-29T08:43:29 Z bharat2002 Relativnost (COCI15_relativnost) C++14
70 / 140
 1413 ms 53240 KB 
/*input
4 2
1 2 3 4
1 2 3 4
1
4 1 1
*/
#include<bits/stdc++.h>
using namespace std;
const int N=1e5 + 100;
const int mod=1e4 + 7;
#define int long long
const int inf=1e18;
#define pii pair<int, int>
#define f first
#define s second 
#define mp make_pair
#define FOR(i, n) for(int i=1;i<=n;i++)
#define TRACE(x) cerr << #x << " = " << x << endl 
//Trace prints the name of the variable and the value.
int n, c;
struct node
{
	int tot, ans[22];
	void calcdp(int a[], int b[])
	{
		for(int i=0;i<=c;i++)
		{
			ans[i]=0;
			for(int j=0;j<=i;j++){
				ans[i]+=a[j]*b[i-j];ans[i]%=mod;
			}
		}
	}
};
node tree[4*N];int a[N], b[N], q;
void build(int i=1, int l=1, int r=n)
{
	if(l==r)
	{
		tree[i].tot=a[l] + b[l];tree[i].ans[1]=a[l];tree[i].ans[0]=b[l];return;
	}
	int mid=(l+r)>>1;
	build(2*i, l, mid);build(2*i+1, mid+1, r);tree[i].calcdp(tree[2*i].ans, tree[2*i+1].ans);
	tree[i].tot=tree[2*i].tot*tree[2*i+1].tot;tree[i].tot%=mod;
}
int ql, qr;
void update(int i=1, int l=1, int r=n)
{
	if(l>qr||r<ql) return;
	if(l==r)
	{
		tree[i].tot=a[l] + b[l];tree[i].ans[1]=a[l];tree[i].ans[0]=b[l];return;
	}
	int mid=(l+r)>>1;
	update(2*i, l, mid);update(2*i+1, mid+1, r);tree[i].calcdp(tree[2*i].ans, tree[2*i+1].ans);
	tree[i].tot=tree[2*i].tot*tree[2*i+1].tot;tree[i].tot%=mod;	
}
signed main()
{
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>c;c--;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++) cin>>b[i];
	build();
	cin>>q;
	while(q--)
	{
		int pos, nl, nr;cin>>pos>>nl>>nr;ql=qr=pos;a[pos]=nl;b[pos]=nr;update();
		int ans=0;
		for(int i=0;i<=c;i++)
		{
			ans+=tree[1].ans[i];ans%=mod;
		}
		ans=tree[1].tot-ans;ans+=mod;ans%=mod;cout<<ans<<endl;
	}
}

Subtask #1
70.0 / 140.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 768 KB Output is correct
2 Correct 11 ms 768 KB Output is correct
3 Correct 15 ms 768 KB Output is correct
4 Correct 301 ms 27768 KB Output is correct
5 Runtime error 686 ms 53240 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 889 ms 52812 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Correct 472 ms 28156 KB Output is correct
8 Runtime error 316 ms 52216 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 528 ms 53240 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 1413 ms 48764 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)