oj.uz

Submission #197746

# Submission time Handle Problem Language Result Execution time Memory
197746 2020-01-22T18:42:50 Z brcode Relativnost (COCI15_relativnost) C++14
0 / 140
 1472 ms 29720 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MOD = 10007;
const int MAXN = 1e5+5;
int seg[2*MAXN][25];
int n,c;
int a[MAXN];
int b[MAXN];
void build(int curr,int l,int r){
    if(l==r){
        seg[curr][0] = b[l];
        seg[curr][1] = a[l];
        seg[curr][0]%=MOD;
        seg[curr][1]%=MOD;
        return;
    }
    cout<<curr<<endl;
    int mid = (l+r)/2;
    build(2*curr,l,mid);
    build(2*curr+1,mid+1,r);
    for(int i=0;i<=c;i++){
        for(int 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(int curr,int l,int r,int target){
    if(l==r){
        seg[curr][0] = b[l];
        seg[curr][1] = a[l];
        seg[curr][0]%=MOD;
        seg[curr][1]%=MOD;
        return;
    }
    
    int mid = (l+r)/2;
    if(target<=mid){
        update(2*curr,l,mid,target);
        for(int i=0;i<=c;i++){
            seg[curr][i] = 0;
        }
        for(int i=0;i<=c;i++){
            for(int 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(int i=0;i<=c;i++){
            seg[curr][i] = 0;
        }
        for(int i=0;i<=c;i++){
            for(int 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(int i=1;i<=n;i++){
        cin>>a[i];
        a[i]%=MOD;
    }
    for(int i=1;i<=n;i++){
        cin>>b[i];
        b[i]%=MOD;
    }
    build(1,1,n);
    int q;
    cin>>q;
    while(q--){
        int pos;
        cin>>pos;
        cin>>a[pos]>>b[pos];
        update(1,1,n,pos);
        cout<<seg[1][c]<<endl;
    }
    
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 632 KB Output isn't correct
2 Incorrect 22 ms 632 KB Output isn't correct
3 Incorrect 33 ms 504 KB Output isn't correct
4 Incorrect 931 ms 14292 KB Output isn't correct
5 Runtime error 330 ms 29600 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 391 ms 29720 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Incorrect 1472 ms 14476 KB Output isn't correct
8 Runtime error 312 ms 29660 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 273 ms 29432 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 317 ms 29336 KB Execution killed with signal 11 (could be triggered by violating memory limits)