Submission #31680

#	Time	Username	Problem	Language	Result	Execution time	Memory
31680		huyxooxooxooxoox	Relativnost (COCI15_relativnost)	C++14	0 / 140	0 ms	1840 KiB

relativnost

//
//  main.cpp
//  Relativnost.cpp
//
//  Created by QuangHuy on 8/30/17.
//  Copyright © 2017 QuangHuy. All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <string>
#include <iomanip>
#include <stack>
#include <deque>
#include <queue>
#define ll int
#define endl '\n'
#define maxN 100001
#define Mod 10007

using namespace std;
ll n,c,Q;
struct Node
{
    ll f[21];
};
Node T[maxN*4];
ll l[maxN*4],r[maxN*4];
ll leaf[maxN*4];
ll a[maxN],b[maxN];
void Combine(ll id)
{
    /*
    for(int i=c;i>=0;i--)
    {
        T[id].f[i]=0;
        for(int j=0;j<=i;j++)
            T[id].f[i]=(T[id].f[i]+T[id*2].f[j]*T[id*2+1].f[i-j])%Mod;
    }*/
    fill_n(&T[id].f[0],sizeof(T[id].f)/sizeof(T[id].f[0]),0);
    for(int i=0;i<=c;++i)
        for(int j=0;j<=c;++j)
            T[id].f[min((i+j),c)]=(T[id].f[min((i+j),c)]+T[id*2].f[j]*T[id*2+1].f[i])%Mod;
    
}

void MakeNode(ll id,ll left,ll right)
{
    l[id]=left;
    r[id]=right;
    if(left==right)
    {
        leaf[left]=id;
        fill_n(&T[id].f[0],sizeof(T[id].f)/sizeof(T[id].f[0]),0);
        T[id].f[0]=b[left]%Mod;
        T[id].f[1]=a[left]%Mod;
        return;
    }
    MakeNode(id*2,left,(left+right)/2);
    MakeNode(id*2+1,(left+right)/2+1,right);
    Combine(id);
}
void InitTree()
{
    MakeNode(1,1,n);
}
void Update(ll p, ll a, ll b)
{
    ll id=leaf[p];
    fill_n(&T[id].f[0],sizeof(T[id].f)/sizeof(T[id].f[0]),0);
    T[id].f[0]=b%Mod;
    T[id].f[1]=a%Mod;
    while(id>1)
    {
        id/=2;
        Combine(id);
    }
    
}
ll id,u,v;
void Solve()
{
    cin>>n>>c;
    for(int i=1;i<=n;++i)
        cin>>a[i];
    
    for(int i=1;i<=n;++i)
        cin>>b[i];
    InitTree();
    cin>>Q;
    for(int i=0;i<Q;++i)
    {
        cin>>id>>u>>v;
        Update(id,u,v);
        /*
        for(int id=1;id<10;id++)
        {
            cout<<l[id]<<" "<<r[id]<<endl;
            for(int j=0;j<=c;j++)
            {
                cout<<T[id].f[j]<<" ";
            }
            cout<<endl;
        }
        */
        cout<<T[1].f[c]<<endl;
        
    
    }
    
    
    
    
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("/Users/quanghuy/Desktop/Input.inp","r", stdin);
    //freopen("/Users/quanghuy/Desktop/Output.out","w", stdout);
    //freopen(".inp","r",stdin);
    //freopen(".out","w",stdout);
    Solve();
}

• Subtask 1: 0 / 140