oj.uz

Submission #153986

# Submission time Handle Problem Language Result Execution time Memory
153986 2019-09-17T16:14:12 Z nicolaalexandra Relativnost (COCI15_relativnost) C++14
0 / 140
 4000 ms 36168 KB 
#include <iostream>
#define DIM 100010
#define MOD 10007
using namespace std;
int aint[4*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 > (dr-st+1))
                continue;
            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;
        }}}
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 > (dr-st+1))
                continue;
            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%MOD,b%MOD);
    }
    build (1,1,n);
    cin>>q;
    for (;q--;){
        cin>>poz>>a>>b;
        nr[poz] = make_pair(a%MOD,b%MOD);
        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 15 ms 632 KB Output isn't correct
2 Incorrect 21 ms 632 KB Output isn't correct
3 Incorrect 36 ms 632 KB Output isn't correct
4 Incorrect 897 ms 19140 KB Output isn't correct
5 Runtime error 2067 ms 36144 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
6 Runtime error 2709 ms 35768 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
7 Incorrect 1406 ms 19428 KB Output isn't correct
8 Runtime error 943 ms 35080 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
9 Runtime error 1599 ms 36168 KB Memory limit exceeded (if you are sure your verdict is not MLE, please contact us)
10 Execution timed out 4037 ms 36020 KB Time limit exceeded