oj.uz

Submission #31670

# Submission time Handle Problem Language Result Execution time Memory
31670 2017-08-30T15:36:04 Z long10024070 Relativnost (COCI15_relativnost) C++11
112 / 140
 4000 ms 19364 KB 
#include <iostream>
#include <cstdio>

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

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

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

void Update(const int &i)
{
    int t = i + n - 1;
    fill(node[t],node[t]+c+1,0);
    node[t][1] = a[i];
    node[t][0] = b[i];
    t /= 2;
    while (t != 0) {
        fill(node[t],node[t]+c+1,0);
        for (int j=0;j<=c;++j)
            for (int 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) % Mod;
            }
        t /= 2;
    }
}

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

void Solve()
{
    int q,p,A,B;
    for (scanf("%d",&q);q>0;--q) {
        //cin >> p >> A >> B;
        scanf("%d%d%d",&p,&A,&B);
        a[p] = A % Mod;
        b[p] = B % Mod;
        Update(p);
        //cout << node[1].f[c] << '\n';
        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 Enter()':
relativnost.cpp:14: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:17:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&a[i]);
                          ^
relativnost.cpp:22: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:53: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:55:33: 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
112.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19364 KB Output is correct
2 Correct 23 ms 19364 KB Output is correct
3 Correct 46 ms 19364 KB Output is correct
4 Correct 869 ms 19364 KB Output is correct
5 Correct 3446 ms 19364 KB Output is correct
6 Execution timed out 4000 ms 19364 KB Execution timed out
7 Correct 2213 ms 19364 KB Output is correct
8 Correct 1313 ms 19364 KB Output is correct
9 Correct 1846 ms 19364 KB Output is correct
10 Execution timed out 4000 ms 19364 KB Execution timed out