oj.uz

Submission #93645

# Submission time Handle Problem Language Result Execution time Memory
93645 2019-01-10T14:09:37 Z ajmasin Relativnost (COCI15_relativnost) C++14
98 / 140
 4000 ms 9204 KB 
#include <bits/stdc++.h>
using namespace std;

#define REP(i, a, b) for(int i = a; i < b; i++)

const int maxn = 100100;
const int maxc = 25;
const int offset = (1<<17);
const int mod = 10007;

int n, c, q;

int niza[maxn];
int nizb[maxn];

int add(int a, int b)
{
    a += b;
    if(a >= mod) a -= mod;
    if(a < 0) a += mod;
    return a;
}

int mult(int a, int b)
{
    return a * b % mod;
}

struct tournament
{
    int brn[maxc][2 * offset];
    void update(int cvor)
    {
        REP(i, 0, c + 1) brn[i][cvor] = 0;
        REP(i, 0, c + 1)
        {
            REP(j, 0, c + 1)
            {
                int suma = min(i + j, c);
                brn[suma][cvor] = add(brn[suma][cvor], mult(brn[i][cvor * 2], brn[j][cvor * 2 + 1]));
            }
        }
        //REP(i, 0, c + 1) cout << brn[i][cvor] << " ";
        //cout << endl;
        return;
    }
}T;

int main()
{
    for(int i = 2 * offset - 1; i > 0; i--) T.brn[0][i] = 1;
    scanf("%d%d", &n, &c);
    int a, b;
    REP(i, 0, n)
    {
        scanf("%d", &niza[i]);
        niza[i] %= mod;
    }
    REP(i, 0, n)
    {
        scanf("%d", &nizb[i]);
        nizb[i] %= mod;
    }
    REP(i, 0, n)
    {
        T.brn[0][i + offset] = nizb[i];
        T.brn[1][i + offset] = niza[i];
        int up = (i + offset) / 2;
        while(up)
        {
            T.update(up);
            up /= 2;
        }
    }
    scanf("%d", &q);
    int p;
    REP(i, 0, q)
    {
        scanf("%d%d%d", &p, &a, &b);
        a %= mod;
        b %= mod;
        p--;
        T.brn[0][p + offset] = b;
        T.brn[1][p + offset] = a;
        p += offset;
        p /= 2;
        while(p)
        {
            T.update(p);
            p /= 2;
        }
        printf("%d\n", T.brn[c][1]);
    }
    return 0;
}

Compilation message

relativnost.cpp: In function 'int main()':
relativnost.cpp:52:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &c);
     ~~~~~^~~~~~~~~~~~~~~~
relativnost.cpp:56:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &niza[i]);
         ~~~~~^~~~~~~~~~~~~~~~
relativnost.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &nizb[i]);
         ~~~~~^~~~~~~~~~~~~~~~
relativnost.cpp:75:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &q);
     ~~~~~^~~~~~~~~~
relativnost.cpp:79:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &p, &a, &b);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
98.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 1784 KB Output is correct
2 Correct 46 ms 1784 KB Output is correct
3 Correct 97 ms 2096 KB Output is correct
4 Correct 1046 ms 4120 KB Output is correct
5 Execution timed out 4029 ms 7532 KB Time limit exceeded
6 Execution timed out 4078 ms 9204 KB Time limit exceeded
7 Correct 3098 ms 5884 KB Output is correct
8 Correct 1597 ms 5672 KB Output is correct
9 Correct 2554 ms 5692 KB Output is correct
10 Execution timed out 4019 ms 8560 KB Time limit exceeded