Submission #153995

#	Time	Username	Problem	Language	Result	Execution time	Memory
153995		Ruxandra985	Relativnost (COCI15_relativnost)	C++14	140 / 140	3501 ms	13388 KiB

relativnost

 
#include <cstdio>
#define MOD 10007
using namespace std;
int aint[21][400010],c;
int a1[100010],b1[100010],curr;
FILE *fin = stdin;
FILE *fout = stdout;
void build (int nod,int st,int dr){
    int mid = (st + dr)/2,x,y,i,j;
    if (st == dr){
        aint[0][nod] = b1[++curr]%MOD;
        aint[1][nod] = a1[curr]%MOD;
        return;
    }
    build (2*nod,st,mid);
    build (2*nod+1,mid+1,dr);
 
    for (i=0;i<=c;i++){
        for (j=0;j<=i;j++){
            if (i!=c)
                aint[i][nod] = (aint[i][nod] + (aint[j][2*nod] * aint[i-j][2*nod+1]))%MOD;
            if (i + j >= c){
                aint[c][nod] = (aint[c][nod] + (aint[i][2*nod] * aint[j][2*nod+1]))%MOD;
                if (i!=j)
                    aint[c][nod] = (aint[c][nod] + (aint[j][2*nod] * aint[i][2*nod+1]))%MOD;
            }
        }
    }
 
 
}
 
void update (int nod,int st,int dr,int p,int x,int y){
    int mid = (st + dr)/2,i,j;
    if (st == dr){
        aint[0][nod] = y%MOD;
        aint[1][nod] = x%MOD;
        return;
    }
    if (p<=mid)
        update (2*nod,st,mid,p,x,y);
    else update (2*nod+1,mid+1,dr,p,x,y);
 
    aint[c][nod] = 0;
    for (i=0;i<=c;i++){
        if (i!=c)
            aint[i][nod] = 0;
        for (j=0;j<=i;j++){
            if (i!=c)
                aint[i][nod] = (aint[i][nod] + (aint[j][2*nod] * aint[i-j][2*nod+1]))%MOD;
            if (i + j >= c){
                aint[c][nod] = (aint[c][nod] + (aint[i][2*nod] * aint[j][2*nod+1]))%MOD;
                if (i!=j)
                    aint[c][nod] = (aint[c][nod] + (aint[j][2*nod] * aint[i][2*nod+1]))%MOD;
            }
        }
    }
 
 
}
 
 
int main()
{
 
    int n,q,p,a,b,i;
    fscanf (fin,"%d%d",&n,&c);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d",&a1[i]);
    for (i=1;i<=n;i++)
        fscanf (fin,"%d",&b1[i]);
    build(1,1,n);
    fscanf (fin,"%d",&q);
    for (;q;q--){
        fscanf (fin,"%d%d%d",&p,&a,&b);
        update (1,1,n,p,a,b);
        fprintf (fout,"%d\n",aint[c][1]);
    }
    return 0;
}

Compilation message (stderr)

relativnost.cpp: In function 'void build(int, int, int)':
relativnost.cpp:11:27: warning: unused variable 'x' [-Wunused-variable]
     int mid = (st + dr)/2,x,y,i,j;
                           ^
relativnost.cpp:11:29: warning: unused variable 'y' [-Wunused-variable]
     int mid = (st + dr)/2,x,y,i,j;
                             ^
relativnost.cpp: In function 'int main()':
relativnost.cpp:69:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d%d",&n,&c);
     ~~~~~~~^~~~~~~~~~~~~~~~~~
relativnost.cpp:71:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&a1[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~
relativnost.cpp:73:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d",&b1[i]);
         ~~~~~~~^~~~~~~~~~~~~~~~~
relativnost.cpp:75:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     fscanf (fin,"%d",&q);
     ~~~~~~~^~~~~~~~~~~~~
relativnost.cpp:77:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         fscanf (fin,"%d%d%d",&p,&a,&b);
         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 140 / 140