Submission #154006

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
154006	2019-09-17T17:02:51 Z	nicolaalexandra	Relativnost (COCI15_relativnost)	C++14	126 / 140	4000 ms	28180 KB

relativnost

/// bn ca trimit de 3 ori de 0 ca nu stiu sa fa o citire
#include <iostream>
#define DIM 100010
#define MOD 10007
using namespace std;
int aint[3*DIM][23];
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<=c;++j){
            int val = i+j;

            if (val > c)
                val = c;
            aint[nod][val] = (aint[nod][val] + aint[nod<<1][i]*aint[(nod<<1)|1][j])%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;++i)
        aint[nod][i] = 0;

    for (int i=0;i<=c;++i){
        for (int j=0;j<=c;++j){
            int val = i+j;

            if (val > c)
                val = c;
            aint[nod][val] = (aint[nod][val] + aint[nod<<1][i]*aint[(nod<<1)|1][j])%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;
        nr[poz] = make_pair(a%MOD,b%MOD);
        update (1,1,n,poz);
        cout<<aint[1][c]<<"\n";
    }

    return 0;
}

Subtask #1

126.0 / 140.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	13 ms	504 KB	Output is correct
2	Correct	20 ms	504 KB	Output is correct
3	Correct	31 ms	504 KB	Output is correct
4	Correct	874 ms	15708 KB	Output is correct
5	Correct	1912 ms	28180 KB	Output is correct
6	Correct	2625 ms	28052 KB	Output is correct
7	Correct	1295 ms	15868 KB	Output is correct
8	Correct	852 ms	27792 KB	Output is correct
9	Correct	1427 ms	28040 KB	Output is correct
10	Execution timed out	4014 ms	28096 KB	Time limit exceeded