oj.uz

Submission #31657

# Submission time Handle Problem Language Result Execution time Memory
31657 2017-08-30T14:18:31 Z long10024070 Relativnost (COCI15_relativnost) C++11
0 / 140
 0 ms 1840 KB 
#include <iostream>
#include <cstdio>

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

const short Mod = 1e4 + 7;
const int maxn = 1e6 + 1;
struct T_node
{
    short l,r,f[21];
};
int n,id[maxn];
short c,a[maxn],b[maxn];
T_node node[maxn*20];

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

void Build_tree(int i, int l, int r)
{
    node[i].l = l;
    node[i].r = r;
    fill(node[i].f,node[i].f+c+1,1);
    if (l == r)
        id[l] = i;
    else {
        Build_tree(i*2,l,(l+r)/2);
        Build_tree(i*2+1,(l+r)/2+1,r);
    }
}

void Update(int i)
{
    if (i == 0)
        return;
    fill(node[i].f,node[i].f+c+1,0);
    if (node[i].l == node[i].r) {
        node[i].f[1] = a[node[i].l] % Mod;
        node[i].f[0] = b[node[i].l] % Mod;
    }
    else
        for (short j=0;j<=c;++j)
            for (short k=0;k<=c;++k) {
                short l = (j + k);
                node[i].f[min(c,l)] = (node[i].f[min(c,l)] + (int)node[i*2].f[j] * node[i*2+1].f[k] % Mod) % Mod;
            }
    Update(i/2);
}

void Init()
{
    Build_tree(1,1,n);
    for (int i=1;i<=n;++i)
        Update(id[i]);
}

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

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

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

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

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 0 ms 1840 KB Execution killed with signal 11 (could be triggered by violating memory limits)