Submission #98704

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
98704	2019-02-25T05:30:08 Z	duy_tran	Relativnost (COCI15_relativnost)	C++14	140 / 140	1835 ms	31796 KB

relativnost

#include<bits/stdc++.h>
using namespace std;

template<typename T> inline void Cin(T &x)
{
    x=0;
    T sign=1;
    char c;

    for(c=getchar();c<'0'||c>'9';c=getchar())
        if(c=='-')sign=-1;

    for(;c>='0'&&c<='9';c=getchar())
        x=x*10+c-'0';

    x*=sign;
}

template<typename T>inline void Out(T x)
{
    if(x==0)return;
    Out(x/10);
    putchar(x%10+'0');
}

template<typename T>inline void Cout(T x)
{
    if(x==0)
    {
        putchar('0');
        return;
    }

    if(x<0)putchar('-'),x=-x;
    Out(x);
}

const int modd=(int)1e4+7;
const int maxn=(int)1e5+50;
int n,c,q,leaf[maxn],a[maxn],b[maxn];
struct X
{
    int l,r,total,f[25],mul;
}tree[4*maxn];

void Combine(int id)
{
    tree[id].total=0;
    for(int i=0;i<c;++i)
    {
        tree[id].f[i]=0;
        for(int j=0;j<=i;++j)
            tree[id].f[i]=(tree[id].f[i]+(tree[id*2].f[j]*tree[id*2+1].f[i-j])%modd)%modd;
        tree[id].total=(tree[id].total+tree[id].f[i])%modd;
    }

    tree[id].mul=(tree[id*2].mul*tree[id*2+1].mul)%modd;
}

void BuildTree(int id,int le,int ri)
{
    tree[id].l=le;
    tree[id].r=ri;

    if(le==ri)
    {
        leaf[le]=id;
        tree[id].f[0]=b[le];
        tree[id].f[1]=a[le];
        tree[id].mul=(a[le]+b[le])%modd;
        return;
    }

    int mid=(le+ri)/2;
    BuildTree(id*2,le,mid);
    BuildTree(id*2+1,mid+1,ri);

    Combine(id);
}

void Up(int id,int ap,int bp)
{
    tree[id].f[0]=bp;
    tree[id].f[1]=ap;
    tree[id].mul=(ap+bp)%modd;
    id/=2;

    while(id>0)
    {
        Combine(id);
        id/=2;
    }
}

int main()
{
    Cin(n);
    Cin(c);

    for(int i=1;i<=n;++i)
    {
        Cin(a[i]);
        a[i]%=modd;
    }

    for(int i=1;i<=n;++i)
    {
        Cin(b[i]);
        b[i]%=modd;
    }

    BuildTree(1,1,n);

    Cin(q);

    for(int i=1;i<=q;++i)
    {
        int p,ap,bp;
        Cin(p);
        Cin(ap);
        Cin(bp);
        ap%=modd;
        bp%=modd;

        Up(leaf[p],ap,bp);

        Cout((tree[1].mul-tree[1].total+modd)%modd);
        putchar('\n');
    }
}

Subtask #1

140.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	640 KB	Output is correct
2	Correct	11 ms	640 KB	Output is correct
3	Correct	13 ms	640 KB	Output is correct
4	Correct	377 ms	16252 KB	Output is correct
5	Correct	868 ms	31480 KB	Output is correct
6	Correct	1262 ms	31796 KB	Output is correct
7	Correct	620 ms	16504 KB	Output is correct
8	Correct	376 ms	31508 KB	Output is correct
9	Correct	691 ms	31588 KB	Output is correct
10	Correct	1835 ms	31548 KB	Output is correct