oj.uz

Submission #197745

# Submission time Handle Problem Language Result Execution time Memory
197745 2020-01-22T18:39:44 Z brcode Relativnost (COCI15_relativnost) C++14
70 / 140
 1291 ms 58232 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 10007;
const long long MAXN = 1e5+5;
long long seg[2*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 760 KB Output is correct
2 Correct 21 ms 760 KB Output is correct
3 Correct 31 ms 760 KB Output is correct
4 Correct 804 ms 27128 KB Output is correct
5 Runtime error 231 ms 57976 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 265 ms 58048 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 1291 ms 27400 KB Output is correct
8 Runtime error 211 ms 58232 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 192 ms 57800 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 252 ms 50884 KB Execution killed with signal 11 (could be triggered by violating memory limits)