oj.uz

답안 #98704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98704 2019-02-25T05:30:08 Z duy_tran Relativnost (COCI15_relativnost) C++14
140 / 140
 1835 ms 31796 KB 
#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

# 결과 실행 시간 메모리 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