oj.uz

Submission #154032

# Submission time Handle Problem Language Result Execution time Memory
154032 2019-09-17T18:44:59 Z nicolaalexandra Relativnost (COCI15_relativnost) C++14
140 / 140
 3721 ms 26300 KB 
#include <iostream>
#define DIM 100002
#define MOD 10007
using namespace std;
int aint[4*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
140.0 / 140.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 504 KB Output is correct
2 Correct 19 ms 504 KB Output is correct
3 Correct 29 ms 504 KB Output is correct
4 Correct 771 ms 12440 KB Output is correct
5 Correct 1818 ms 25888 KB Output is correct
6 Correct 2441 ms 25648 KB Output is correct
7 Correct 1265 ms 12436 KB Output is correct
8 Correct 870 ms 24992 KB Output is correct
9 Correct 1362 ms 26300 KB Output is correct
10 Correct 3721 ms 26268 KB Output is correct