oj.uz

Submission #371261

# Submission time Handle Problem Language Result Execution time Memory
371261 2021-02-26T10:08:42 Z Atill83 Relativnost (COCI15_relativnost) C++14
140 / 140
 3832 ms 23276 KB 
#include <bits/stdc++.h>
#define ff first
#define ss second
#define endl '\n'
using namespace std;
const long long INF = (long long) 1e18;
const int mod = (int) 1e4+7;
const int MAXN = (int) 1e5+5;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
int n, c;
int a[MAXN], b[MAXN];


int t[4*MAXN][21];

void build(int v, int tl, int tr){
    if(tl == tr){
        t[v][0] = b[tl];
        t[v][1] = a[tl];
    }else{
        int tm = (tl + tr) / 2;
        build(2*v, tl, tm);
        build(2*v + 1, tm + 1, tr);
        for(int j = 0; j <= c; j++)
            t[v][j] = 0;
        for(int i = 0; i <= c; i++){
            for(int j = 0; j <= c; j++){
                t[v][min(c, (i + j))] = (t[v][min(c, (i + j))] + t[2*v][i] * t[2*v + 1][j] % mod) % mod;
            }
        }
    }
}

void upd(int v, int tl, int tr, int pos){
    if(tl == tr){
        t[v][0] = b[tl];
        t[v][1] = a[tl];
    }else{
        int tm = (tl + tr) / 2;
        if(pos <= tm)
            upd(2*v, tl, tm, pos);
        else
            upd(2*v + 1, tm + 1, tr, pos);
        for(int j = 0; j <= c; j++)
            t[v][j] = 0;
        for(int i = 0; i <= c; i++){
            for(int j = 0; j <= c; j++){
                t[v][min(c, (i + j))] = (t[v][min(c, (i + j))] + t[2*v][i] * t[2*v + 1][j] % mod) % mod;
            }
        }
    }
}


int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);

    #ifdef Local
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/int.txt","r",stdin);
        freopen("C:/Users/Admin/Desktop/Yazilim/C/IO/out.txt","w",stdout);
    #endif

    cin>>n>>c;

    for(int i = 0; i < n; i++){
        cin>>a[i];   
        a[i] %= mod;
    }
    for(int i = 0; i < n; i++){
        cin>>b[i];
        b[i] %= mod;
    }

    build(1, 0, n - 1);
 
    int q;
    cin>>q;

    for(int i = 0; i < q; i++){
        int idx;
        cin>>idx;
        idx--;
        cin>>a[idx]>>b[idx];
        a[idx] %= mod;
        b[idx] %= mod;
        upd(1, 0, n - 1, idx);
        cout<<t[1][c]<<endl;
    }

    #ifdef Local
        cout<<endl<<fixed<<setprecision(2)<<1000.0 * clock() / CLOCKS_PER_SEC<< " milliseconds ";
    #endif
}

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 492 KB Output is correct
2 Correct 14 ms 492 KB Output is correct
3 Correct 32 ms 492 KB Output is correct
4 Correct 477 ms 11884 KB Output is correct
5 Correct 1614 ms 23020 KB Output is correct
6 Correct 2432 ms 23020 KB Output is correct
7 Correct 1053 ms 12012 KB Output is correct
8 Correct 544 ms 22876 KB Output is correct
9 Correct 1016 ms 23120 KB Output is correct
10 Correct 3832 ms 23276 KB Output is correct