oj.uz

Submission #164321

# Submission time Handle Problem Language Result Execution time Memory
164321 2019-11-19T11:41:02 Z beso123 Relativnost (COCI15_relativnost) C++14
70 / 140
 4000 ms 65532 KB 
#include <bits/stdc++.h>
#define int long long
#define mod 10007
using namespace std;
int n,m,Q,a[100005],b[100005],t[400005][30],sum;
void update(int v){
for(int k=0;k<=m;k++)
        t[v][k]=0;
  for(int i=0;i<=m;++i)
    for(int j=0;j<=m;++j){
      t[v][min(i+j,m)]+=((t[v*2][i]%mod)*(t[v*2+1][j])%mod);
      t[v][min(i+j,m)]%=mod;
  }

}
void Build(int v,int i,int j){
    if(i==j){
        t[v][0]=b[i]%mod;
        t[v][1]=a[i]%mod;
        return;
    }
    int mid=(i+j)/2;
    Build(v*2,i,mid);
    Build(v*2+1,mid+1,j);
   update(v);
}
void UPD(int v,int i,int j,int pos){
    if(i==j){
        t[v][0]=b[i]%mod;
        t[v][1]=a[i]%mod;
        return;
    }
    int mid=(i+j)/2;
    if(pos<=mid)
        UPD(v*2,i,mid,pos);
    else
        UPD(v*2+1,mid+1,j,pos);
    update(v);
}
main(){
cin>>n>>m;
for(int k=1;k<=n;k++){
    cin>>a[k];
    a[k]%=mod;
}
for(int k=1;k<=n;k++){
    cin>>b[k];
    b[k]%=mod;
}
Build(1,1,n);
cin>>Q;
while(Q--){
   int x,na,nb;
   cin>>x>>na>>nb;
   a[x]=na%mod;
   b[x]=nb%mod;
    UPD(1,1,n,x);
    cout<<t[1][m]%mod<<endl;
}
return 0;
}

Compilation message

relativnost.cpp:40:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 760 KB Output is correct
2 Correct 24 ms 888 KB Output is correct
3 Correct 39 ms 888 KB Output is correct
4 Correct 940 ms 32484 KB Output is correct
5 Runtime error 2557 ms 65532 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 3391 ms 65484 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Correct 1652 ms 32668 KB Output is correct
8 Runtime error 1140 ms 64768 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 1759 ms 65528 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Execution timed out 4017 ms 54140 KB Time limit exceeded