oj.uz

Submission #197744

# Submission time Handle Problem Language Result Execution time Memory
197744 2020-01-22T18:25:33 Z brcode Relativnost (COCI15_relativnost) C++14
70 / 140
 3941 ms 57448 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 10007;
const long long MAXN = 1e5+5;
long long seg[4*MAXN][25];
long long n,c;
long long a[MAXN];
long long b[MAXN];
void build(long long curr,long long l,long long r){
    if(l==r){
        seg[curr][0] = b[l];
        seg[curr][1] = a[l];
        seg[curr][0]%=MOD;
        seg[curr][1]%=MOD;
        return;
    }
    long long mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    for(long long i=0;i<=c;i++){
        for(long long j=0;j<=c;j++){
            seg[curr][min(i+j,c)] += (1LL*seg[2*curr][i]*seg[2*curr+1][j]);
            seg[curr][min(i+j,c)]%=MOD;
        }
    }
    
}
void update(long long curr,long long l,long long r,long long target){
    if(l==r){
        seg[curr][0] = b[l];
        seg[curr][1] = a[l];
        seg[curr][0]%=MOD;
        seg[curr][1]%=MOD;
        return;
    }
    long long mid = (l+r)/2;
    if(target<=mid){
        update(2*curr,l,mid,target);
        for(long long i=0;i<=c;i++){
            seg[curr][i] = 0;
        }
        for(long long i=0;i<=c;i++){
            for(long long j=0;j<=c;j++){
                seg[curr][min(i+j,c)] += (1LL*seg[2*curr][i]*seg[2*curr+1][j]);
                seg[curr][min(i+j,c)]%=MOD;
            }
        }
    }else{
        update(2*curr+1,mid+1,r,target);
        for(long long i=0;i<=c;i++){
            seg[curr][i] = 0;
        }
        for(long long i=0;i<=c;i++){
            for(long long j=0;j<=c;j++){
                seg[curr][min(i+j,c)] += (1LL*seg[2*curr][i]*seg[2*curr+1][j]);
                seg[curr][min(i+j,c)]%=MOD;
            }
        }
    }
}
int main(){
    cin>>n>>c;
    for(long long i=1;i<=n;i++){
        cin>>a[i];
    }
    for(long long i=1;i<=n;i++){
        cin>>b[i];
    }
    build(1,1,n);
    long long q;
    cin>>q;
    while(q--){
        long long pos;
        cin>>pos;
        cin>>a[pos]>>b[pos];
        update(1,1,n,pos);
        cout<<seg[1][c]<<endl;
    }
    
}

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 888 KB Output is correct
2 Correct 20 ms 764 KB Output is correct
3 Correct 30 ms 760 KB Output is correct
4 Correct 856 ms 29932 KB Output is correct
5 Runtime error 1924 ms 57224 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 2595 ms 56964 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Correct 1318 ms 30296 KB Output is correct
8 Runtime error 871 ms 56472 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 1497 ms 57448 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Runtime error 3941 ms 50920 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)