Submission #31678

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
31678	2017-08-30T15:45:20 Z	long10024070	Relativnost (COCI15_relativnost)	C++11	112 / 140	4000 ms	19364 KB

relativnost

#include <iostream>
#include <cstdio>

using namespace std;
const string TASK = "Relativnost";

const int Mod = 1e4 + 7;
const int maxn = 1e5 + 1;
int n,c,i,a[maxn],b[maxn],node[maxn*2][21],t,j,k;

void Enter()
{
    scanf("%d%d",&n,&c);
    for (i=1;i<=n;++i)
        scanf("%d",&a[i]);
    for (i=1;i<=n;++i)
        scanf("%d",&b[i]);
}

void Update()
{
    t = i + n - 1;
    for (j=2;j<=c;++j)
        node[t][j] = 0;
    node[t][1] = a[i] % Mod;
    node[t][0] = b[i] % Mod;
    t >>= 1;
    while (t != 0) {
        for (j=0;j<=c;++j)
            node[t][j] = 0;
        for (j=0;j<=c;++j)
            for (k=0;k<=c;++k) {
                node[t][min(c,j+k)] = (node[t][min(c,j+k)] + node[t*2][j] * node[t*2+1][k]) % Mod;
            }
        t >>= 1;
    }
}

void Init()
{
    for (i=1;i<=n;++i)
        Update();
}

void Solve()
{
    int q,A,B;
    for (scanf("%d",&q);q>0;--q) {
        scanf("%d",&i);
        scanf("%d%d",&a[i],&b[i]);
        Update();
        printf("%d\n",node[1][c]);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    //cin.tie(NULL);
    //cout.tie(NULL);

    //freopen((TASK+".INP").c_str(),"r",stdin);
    //freopen((TASK+".OUT").c_str(),"w",stdout);

    Enter();
    Init();
    Solve();
}

Compilation message

relativnost.cpp: In function 'void Solve()':
relativnost.cpp:47:11: warning: unused variable 'A' [-Wunused-variable]
     int q,A,B;
           ^
relativnost.cpp:47:13: warning: unused variable 'B' [-Wunused-variable]
     int q,A,B;
             ^
relativnost.cpp: In function 'void Enter()':
relativnost.cpp:13:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&c);
                        ^
relativnost.cpp:15:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
relativnost.cpp:17:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&b[i]);
                          ^
relativnost.cpp: In function 'void Solve()':
relativnost.cpp:48:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (scanf("%d",&q);q>0;--q) {
                        ^
relativnost.cpp:49:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&i);
                       ^
relativnost.cpp:50:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&a[i],&b[i]);
                                  ^

Subtask #1

112.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	19364 KB	Output is correct
2	Correct	13 ms	19364 KB	Output is correct
3	Correct	36 ms	19364 KB	Output is correct
4	Correct	726 ms	19364 KB	Output is correct
5	Correct	2916 ms	19364 KB	Output is correct
6	Execution timed out	4000 ms	19364 KB	Execution timed out
7	Correct	1803 ms	19364 KB	Output is correct
8	Correct	1086 ms	19364 KB	Output is correct
9	Correct	1546 ms	19364 KB	Output is correct
10	Execution timed out	4000 ms	19364 KB	Execution timed out