oj.uz

Submission #79829

# Submission time Handle Problem Language Result Execution time Memory
79829 2018-10-16T17:08:40 Z KLPP Relativnost (COCI15_relativnost) C++14
70 / 140
 3928 ms 33792 KB 
#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;
typedef long long int lld;
#define MOD 10007
int n,c;
int Segtree[1000000][21];
int A[100010];
int B[100010];
void build(int a, int b, int node){
	if(a==b){
		for(int i=0;i<=c;i++){
			Segtree[node][i]=0;
		}
		Segtree[node][0]=B[a]%MOD;
		Segtree[node][1]=A[a]%MOD;
		return;
	}
	int mid=(a+b)/2;
	build(a,mid,2*node);
	build(mid+1,b,2*node+1);
	for(int i=0;i<=c;i++){
		Segtree[node][i]=0;
	}
	for(int i=0;i<=c;i++){
		for(int j=0;j<=c;j++){
			Segtree[node][min(i+j,c)]+=Segtree[2*node][i]*Segtree[2*node+1][j];
			Segtree[node][min(i+j,c)]%=MOD;
		}
	}
}
void update(int a,int b, int node, int x){
	//cout<<a<<" "<<b<<endl;
	if(x<a || b<x)return;
	if(a==b){
		for(int i=0;i<=c;i++){
			Segtree[node][i]=0;
		}
		Segtree[node][0]=B[a]%MOD;
		Segtree[node][1]=A[a]%MOD;
		return;
	}
	int mid=(a+b)/2;
	update(a,mid,2*node,x);
	update(mid+1,b,2*node+1,x);
	for(int i=0;i<=c;i++){
		Segtree[node][i]=0;
	}
	for(int i=0;i<=c;i++){
		for(int j=0;j<=c;j++){
			Segtree[node][min(i+j,c)]+=Segtree[2*node][i]*Segtree[2*node+1][j];
			Segtree[node][min(i+j,c)]%=MOD;
		}
	}
}

int main(){
	cin>>n>>c;
	for(int i=0;i<n;i++)cin>>A[i];
	for(int i=0;i<n;i++)cin>>B[i];
	build(0,n-1,1);
	int q;
	cin>>q;
	while(q--){
		int x;
		cin>>x;
		x--;
		lld y,z;
		cin>>y>>z;
		A[x]=y;
		B[x]=z;
		update(0,n-1,1,x);
		cout<<Segtree[1][c]<<endl;
	}
	return 0;
}

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 504 KB Output is correct
2 Correct 17 ms 676 KB Output is correct
3 Correct 29 ms 676 KB Output is correct
4 Correct 636 ms 14648 KB Output is correct
5 Correct 1737 ms 29740 KB Output is correct
6 Runtime error 2457 ms 32996 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
7 Runtime error 1168 ms 32996 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
8 Runtime error 770 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
9 Runtime error 1263 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
10 Runtime error 3928 ms 33792 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.