oj.uz

Submission #31666

# Submission time Handle Problem Language Result Execution time Memory
31666 2017-08-30T15:29:11 Z long10024070 Relativnost (COCI15_relativnost) C++11
42 / 140
 3376 ms 19752 KB 
#include <iostream>
#include <cstdio>

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

const int Mod = 1e4 + 7;
const int maxn = 1e5 + 1;
struct T_node
{
    int f[21];
};
int n,id[maxn];
int c,a[maxn],b[maxn];
T_node node[maxn*2];

void Enter()
{
    cin >> n >> c;
    int x;
    for (int i=1;i<=n;++i) {
        cin >> x;
        a[i] = x % Mod;
    }
    for (int i=1;i<=n;++i) {
        cin >> x;
        b[i] = x % Mod;
    }
}

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

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

void Solve()
{
    int q,p,A,B;
    for (cin>>q;q>0;--q) {
        cin >> p >> A >> B;
        a[p] = A % Mod;
        b[p] = B % Mod;
        Update(p);
        cout << node[1].f[c] << '\n';
    }
}

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();
}

Subtask #1
42.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 19752 KB Output is correct
2 Correct 19 ms 19752 KB Output is correct
3 Correct 39 ms 19752 KB Output is correct
4 Runtime error 349 ms 19752 KB Execution killed because of forbidden syscall writev (20)
5 Runtime error 1723 ms 19752 KB Execution killed because of forbidden syscall writev (20)
6 Runtime error 3376 ms 19752 KB Execution killed because of forbidden syscall writev (20)
7 Runtime error 1106 ms 19752 KB Execution killed because of forbidden syscall writev (20)
8 Runtime error 773 ms 19752 KB Execution killed because of forbidden syscall writev (20)
9 Runtime error 736 ms 19752 KB Execution killed because of forbidden syscall writev (20)
10 Runtime error 3159 ms 19752 KB Execution killed because of forbidden syscall writev (20)