oj.uz

Submission #973796

# Submission time Handle Problem Language Result Execution time Memory
973796 2024-05-02T11:02:26 Z sleepntsheep Relativnost (COCI15_relativnost) C
140 / 140
 2673 ms 17200 KB 
#pragma GCC optimize("O3,unroll-loops")
#include <stdio.h>

#define N 100000
#define C 20

const long long MOD = 10007;

int q, n, c, a[N], b[N], p, aa, bb;
int t[N<<1][C+1];

void base(int i)
{
    t[i+n][0] = b[i] % MOD;
    t[i+n][1] = a[i] % MOD;
}

void pul(int i)
{
    for (int j = 0; j <= c; ++j)
        t[i][j] = 0;
    for (int j = 0; j <= c; ++j)
    {
        for (int k = 0; k <= c; ++k)
        {
            int l = j+k<=c?j+k:c;
            t[i][l] = (t[i][l] + t[i<<1][j] * 1ll * t[i<<1|1][k]) % MOD;
        }
    }
}

int main()
{
    scanf("%d%d",&n,&c);

    for (int i = 0; i < n; ++i) scanf("%d", a+i);
    for (int i = 0; i < n; ++i) scanf("%d", b+i), base(i);
    for (int i = n; --i;) pul(i);

    scanf("%d", &q);
    while (q--)
    {
        scanf("%d%d%d", &p, &aa, &bb), --p;
        a[p] = aa, b[p] = bb;
        base(p);
        for (p+=n;p>>=1;) pul(p);
        printf("%d\n", t[1][c]);
    }
}

Compilation message

relativnost.c: In function 'main':
relativnost.c:34:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |     scanf("%d%d",&n,&c);
      |     ^~~~~~~~~~~~~~~~~~~
relativnost.c:36:33: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |     for (int i = 0; i < n; ++i) scanf("%d", a+i);
      |                                 ^~~~~~~~~~~~~~~~
relativnost.c:37:33: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |     for (int i = 0; i < n; ++i) scanf("%d", b+i), base(i);
      |                                 ^~~~~~~~~~~~~~~~
relativnost.c:40:5: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |     scanf("%d", &q);
      |     ^~~~~~~~~~~~~~~
relativnost.c:43:9: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |         scanf("%d%d%d", &p, &aa, &bb), --p;
      |         ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 10 ms 572 KB Output is correct
3 Correct 20 ms 348 KB Output is correct
4 Correct 297 ms 10320 KB Output is correct
5 Correct 1091 ms 17108 KB Output is correct
6 Correct 1653 ms 16976 KB Output is correct
7 Correct 718 ms 12564 KB Output is correct
8 Correct 366 ms 17200 KB Output is correct
9 Correct 664 ms 14928 KB Output is correct
10 Correct 2673 ms 14992 KB Output is correct