Submission #371259

#	Time	Username	Problem	Language	Result	Execution time	Memory
371259		Atill83	Relativnost (COCI15_relativnost)	C++14	42 / 140	3916 ms	25460 KiB

relativnost

#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];   
    for(int i = 0; i < n; i++)
        cin>>b[i];

    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: 42 / 140