oj.uz

Submission #153990

# Submission time Handle Problem Language Result Execution time Memory
153990 2019-09-17T16:22:17 Z Ruxandra985 Relativnost (COCI15_relativnost) C++14
126 / 140
 2063 ms 13220 KB 
/// daca nu iau tle sincer nu stiu

#include <cstdio>
#define MOD 10007
using namespace std;
int aint[20][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
126.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 504 KB Output is correct
2 Correct 13 ms 504 KB Output is correct
3 Correct 24 ms 508 KB Output is correct
4 Correct 398 ms 4548 KB Output is correct
5 Correct 1375 ms 10500 KB Output is correct
6 Correct 2063 ms 13220 KB Output is correct
7 Correct 876 ms 5784 KB Output is correct
8 Correct 508 ms 7820 KB Output is correct
9 Correct 873 ms 8460 KB Output is correct
10 Runtime error 32 ms 2452 KB Execution killed with signal 11 (could be triggered by violating memory limits)