oj.uz

Submission #154031

# Submission time Handle Problem Language Result Execution time Memory
154031 2019-09-17T18:43:53 Z nicolaalexandra Relativnost (COCI15_relativnost) C++14
70 / 140
 1230 ms 27948 KB 
#include <iostream>
#define DIM 100002
#define MOD 10007
using namespace std;
int aint[2*DIM][22];
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%MOD;
        aint[nod][1] = nr[st].first%MOD; /// 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+]  - sa am cel putin c pers care ia tablou
    for (int i=0;i<=c;i++)
        aint[nod][i] = 0;
    for (int i=0;i<=c;i++){
        for (int j=0;j<=i;j++){
            int val = i+j;
            if (i < c)
                aint[nod][i] = (aint[nod][i] + aint[nod<<1][j]*aint[(nod<<1)|1][i-j])%MOD;
            if (val >= c){
                val = c;
                aint[nod][val] = (aint[nod][val] + aint[nod<<1][i]*aint[(nod<<1)|1][j])%MOD;
                if (i != j)
                    aint[nod][val] = (aint[nod][val] + aint[nod<<1][j]*aint[(nod<<1)|1][i])%MOD;
            }}}}
void update (int nod, int st, int dr, int poz, int a, int b){
    if (st == dr){
        aint[nod][0] = b;
        aint[nod][1] = a;
        return;
    }
    int mid = (st+dr)>>1;
    if (poz <= mid)
        update (nod<<1,st,mid,poz,a,b);
    else update ((nod<<1)|1,mid+1,dr,poz,a,b);

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

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



    return 0;
}

Subtask #1
70.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 508 KB Output is correct
2 Correct 19 ms 576 KB Output is correct
3 Correct 29 ms 504 KB Output is correct
4 Correct 774 ms 15152 KB Output is correct
5 Runtime error 204 ms 27868 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 239 ms 27948 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Correct 1230 ms 15236 KB Output is correct
8 Runtime error 185 ms 27916 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 155 ms 27428 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 207 ms 27264 KB Execution killed with signal 11 (could be triggered by violating memory limits)