oj.uz

Submission #153984

# Submission time Handle Problem Language Result Execution time Memory
153984 2019-09-17T16:08:50 Z nicolaalexandra Relativnost (COCI15_relativnost) C++14
0 / 140
 209 ms 19372 KB 
#include <iostream>
#define DIM 100010
#define MOD 10007
using namespace std;
int aint[DIM][30];
pair <int,int> nr[DIM];
int n,i,q,a,b,c,poz;
void build (int nod, int st, int dr){
    if (st == dr){
        aint[nod][0] = nr[st].second;
        aint[nod][1] = nr[st].first; /// am o sg pers care ia tablou colorat
        return;
    }
    int mid = (st+dr)>>1;
    build (nod<<1,st,mid);
    build ((nod<<1)|1,mid+1,dr);
    /// aint[i][j] j <= c - sa am exact j pers care ia tablou, restul nu
    /// aint[i][c+1]  - sa am cel putin c+1 pers care ia tablou
    for (int i=0;i<=c+1;i++){
        for (int j=0;j<=c+1;j++){
            int val = i+j;
            if (val > c+1)
                val = c+1;
            if (val > (dr-st+1))
                continue;
            aint[nod][val] = (aint[nod][val] + 1LL*aint[nod<<1][i]*aint[(nod<<1)|1][j]%MOD)%MOD;
        }}}
void update (int nod, int st, int dr, int poz){
    if (st == dr){
        aint[nod][0] = nr[poz].second;
        aint[nod][1] = nr[poz].first;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz);
    else update ((nod<<1)|1,mid+1,dr,poz);

    for (int i=0;i<=c+1;i++)
        aint[nod][i] = 0;

    for (int i=0;i<=c+1;i++){
        for (int j=0;j<=c+1;j++){
            int val = i+j;
            if (val > c+1)
                val = c+1;
            aint[nod][val] = (aint[nod][val] + 1LL*aint[nod<<1][i]*aint[(nod<<1)|1][j]%MOD)%MOD;
        }}}
int main (){

    cin>>n>>c;
    for (i=1;i<=n;i++){
        cin>>a>>b;
        nr[i] = make_pair(a,b);
    }
    build (1,1,n);
    cin>>q;
    for (;q--;){
        cin>>poz>>a>>b;
        nr[poz] = make_pair(a,b);
        update (1,1,n,poz);
        cout<<(aint[1][c]+aint[1][c+1])%MOD<<"\n";
    }




    return 0;
}

Subtask #1
0 / 140.0

# Verdict Execution time Memory Grader output
1 Incorrect 16 ms 632 KB Output isn't correct
2 Incorrect 23 ms 632 KB Output isn't correct
3 Incorrect 37 ms 732 KB Output isn't correct
4 Runtime error 106 ms 19052 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 133 ms 3832 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 209 ms 3820 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 131 ms 19372 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 141 ms 3960 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 112 ms 3448 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 107 ms 3096 KB Execution killed with signal 11 (could be triggered by violating memory limits)