답안 #153995

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
153995	2019-09-17T16:30:46 Z	Ruxandra985	Relativnost (COCI15_relativnost)	C++14	140 / 140	3501 ms	13388 KB

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

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.0 / 140.0

#	결과	실행 시간	메모리	Grader output
1	Correct	9 ms	376 KB	Output is correct
2	Correct	14 ms	504 KB	Output is correct
3	Correct	30 ms	504 KB	Output is correct
4	Correct	408 ms	3704 KB	Output is correct
5	Correct	1398 ms	9812 KB	Output is correct
6	Correct	2089 ms	12444 KB	Output is correct
7	Correct	881 ms	5112 KB	Output is correct
8	Correct	473 ms	7032 KB	Output is correct
9	Correct	912 ms	7780 KB	Output is correct
10	Correct	3501 ms	13388 KB	Output is correct