Submission #331816

#	Time	Username	Problem	Language	Result	Execution time	Memory
331816		Ruxandra985	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	183 ms	25452 KiB

lucky

/**
* user:  nanu-c77
* fname: Ruxandra Laura
* lname: Nanu
* task:  lucky
* score: 100.0
* date:  2019-10-10 08:55:53.410673
*/
#include <cstdio>
#include <vector>
#include <algorithm>
#define DIMN 100010
#define MOD 1000000007
using namespace std;
int dpst[2][2][2],n,q;
char s[DIMN];
long long aint[4*DIMN][12];
long long sol[12],sa[12];
int ok;
vector <pair <int,int> > stari[12];
int calcul_dp_subtask(){

    int i,curr,j;
    /// este prefix = 1
    for (i=0;i<s[1];i++)
        dpst[1][0][(i==1)] ++;
    dpst[1][1][(s[1] == 1)] = 1;

    for (i=2;i<=n;i++){
        curr = (i&1);
        dpst[curr][0][0] = dpst[curr][0][1] = dpst[curr][1][0] = dpst[curr][1][1] = 0;
        if (s[i]==3 && s[i-1] == 1)
            dpst[curr][1][0] = 0; /// nu mai poi continua prefixul
        else dpst[curr][1][(s[i]==1)] = dpst[1-curr][1][(s[i-1] == 1)];
        /// acum nu mai vrem sa fie prefix
        for (j=0;j<10;j++){
            if (j!=3)/// iei orice
                dpst[curr][0][(j==1)] =((dpst[curr][0][(j==1)] + dpst[1-curr][0][0]) % MOD + dpst[1-curr][0][1])%MOD;
            else dpst[curr][0][(j==1)] =(dpst[curr][0][(j==1)] + dpst[1-curr][0][0]) % MOD;
        }
        for (j=0;j<s[i];j++){
            if (j!=3)/// iei orice
                dpst[curr][0][(j==1)] =((dpst[curr][0][(j==1)] + dpst[1-curr][1][0]) % MOD + dpst[1-curr][1][1])%MOD;
            else dpst[curr][0][(j==1)] =(dpst[curr][0][(j==1)] + dpst[1-curr][1][0]) % MOD;
        }
    }
    return ((dpst[n%2][0][0] + dpst[n%2][0][1] )%MOD + (dpst[n%2][1][0] + dpst[n%2][1][1] )%MOD);

}

int state (int x , int y , int z){
    return x * 4 + z + 2*y;
}

void compatibil (){
    int x,y,z,xx,yy,zz,xf,yf,zf;
    for (x=0;x<3;x++){
        for (xx=0;xx<3;xx++){
            for (y=0;y<2;y++){
                for (yy=0;yy<2;yy++){
                    for (z=0;z<2;z++){
                        for (zz=0;zz<2;zz++){
                            /// este xyz compatibil cu xx yy zz?
                            if (z && yy) /// contine 13
                                continue;
                            if (!x){
                                xf = xx;
                            }
                            else if (x == 1)
                                xf = 1;
                            else xf = 2;

                            yf = y;

                            zf = zz;

                            stari[state(xf,yf,zf)].push_back(make_pair(state(x,y,z) , state(xx,yy,zz)));

                        }
                    }
                }
            }
        }
    }
}


void build (int nod,int st,int dr ){
    int mid = (st + dr)/2,i,j,x,y;
    if (st==dr){
        for (i=0;i<10;i++){
            if (i<s[st]){
                if (i==1)
                    aint[nod][5]++;
                else if (i==3)
                    aint[nod][6]++;
                else aint[nod][4]++;
            }
            else if (i==s[st]){
                if (i==1)
                    aint[nod][1]++;
                else if (i==3)
                    aint[nod][2]++;
                else aint[nod][0]++;
            }
            else {
                if (i==1)
                    aint[nod][9]++;
                else if (i==3)
                    aint[nod][10]++;
                else aint[nod][8]++;
            }
        }
        return;
    }
    build(2*nod,st,mid);
    build(2*nod+1,mid+1,dr);
    ///LE COMBINI
    for (i=0;i<12;i++){
        for (j=0;j<stari[i].size();j++){
            x = stari[i][j].first;
            y = stari[i][j].second;
            aint[nod][i] = (aint[nod][i] + (aint[2*nod][x] * aint[2*nod+1][y])%MOD)%MOD;

        }
    }

}

void query (int nod,int st,int dr,int x,int y){
    int mid = (st + dr)/2,i,j,xx,yy;
    if (x<=st && dr<=y){
        if (!ok){
            for (i=0;i<12;i++)
                sol[i] = aint[nod][i];
            ok = 1;
            return;
        }
        for (i=0;i<12;i++){
            sa[i] = sol[i];
            sol[i] = 0;
        }
        for (i=0;i<12;i++){
            for (j=0;j<stari[i].size();j++){
                xx = stari[i][j].first;
                yy = stari[i][j].second;
                sol[i] = (sol[i] + (sa[xx] * aint[nod][yy])%MOD)%MOD;

            }
        }
        return;
    }
    if (x<=mid)
        query(2*nod,st,mid,x,y);
    if (mid+1<=y)
        query(2*nod+1,mid+1,dr,x,y);

}

void update (int nod,int st,int dr,int p,int cf){
    int mid = (st + dr)/2,i,j,x,y;
    if (st==dr){
        s[st] = cf;
        for (i=0;i<12;i++)
            aint[nod][i] = 0;
        for (i=0;i<10;i++){
            if (i<s[st]){
                if (i==1)
                    aint[nod][5]++;
                else if (i==3)
                    aint[nod][6]++;
                else aint[nod][4]++;
            }
            else if (i==s[st]){
                if (i==1)
                    aint[nod][1]++;
                else if (i==3)
                    aint[nod][2]++;
                else aint[nod][0]++;
            }
            else {
                if (i==1)
                    aint[nod][9]++;
                else if (i==3)
                    aint[nod][10]++;
                else aint[nod][8]++;
            }
        }
        return;
    }
    if (p<=mid)
        update(2*nod,st,mid,p,cf);
    else update(2*nod+1,mid+1,dr,p,cf);
    ///LE COMBINI
    for (i=0;i<12;i++){
        aint[nod][i] = 0;
        for (j=0;j<stari[i].size();j++){
            x = stari[i][j].first;
            y = stari[i][j].second;
            aint[nod][i] = (aint[nod][i] + (aint[2*nod][x] * aint[2*nod+1][y])%MOD)%MOD;

        }
    }

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int q,t,a,b,i;
    fscanf (fin,"%d%d\n",&n,&q);
    fgets (s+1,DIMN,fin);
    for (int i=1;i<=n;i++)
        s[i]-='0';
    if (!q){
        fprintf (fout,"%d",calcul_dp_subtask());
        return 0;
    }
    compatibil(); /// build graf stari
    build(1,1,n);
    long long sum = 0;
    for (i=0;i<8;i++){
        sum = (sum + aint[1][i])%MOD;
    }
    fprintf (fout,"%lld\n",sum);
    for (;q;q--){
        fscanf (fin,"%d%d%d",&t,&a,&b);
        if (t==1){ /// query interval ab
            ok = 0;
            for (i=0;i<12;i++)
                sol[i] = 0;
            query(1,1,n,a,b);
            long long sum = 0;
            for (i=0;i<8;i++){
                sum = (sum + sol[i])%MOD;
            }
            fprintf (fout,"%lld\n",sum);
        }
        else { /// update element
            update (1,1,n,a,b);
        }
    }
    return 0;
}

Compilation message (stderr)

lucky.cpp: In function 'void build(int, int, int)':
lucky.cpp:120:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for (j=0;j<stari[i].size();j++){
      |                  ~^~~~~~~~~~~~~~~~
lucky.cpp: In function 'void query(int, int, int, int, int)':
lucky.cpp:144:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |             for (j=0;j<stari[i].size();j++){
      |                      ~^~~~~~~~~~~~~~~~
lucky.cpp: In function 'void update(int, int, int, int, int)':
lucky.cpp:197:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  197 |         for (j=0;j<stari[i].size();j++){
      |                  ~^~~~~~~~~~~~~~~~
lucky.cpp: In function 'int main()':
lucky.cpp:211:12: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  211 |     fscanf (fin,"%d%d\n",&n,&q);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
lucky.cpp:212:11: warning: ignoring return value of 'char* fgets(char*, int, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
  212 |     fgets (s+1,DIMN,fin);
      |     ~~~~~~^~~~~~~~~~~~~~
lucky.cpp:227:16: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  227 |         fscanf (fin,"%d%d%d",&t,&a,&b);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/stdio.h:862,
                 from /usr/include/c++/9/cstdio:42,
                 from lucky.cpp:9:
In function 'char* fgets(char*, int, FILE*)',
    inlined from 'int main()' at lucky.cpp:212:11:
/usr/include/x86_64-linux-gnu/bits/stdio2.h:260:26: warning: call to '__fgets_chk_warn' declared with attribute warning: fgets called with bigger size than length of destination buffer [-Wattribute-warning]
  260 |  return __fgets_chk_warn (__s, __bos (__s), __n, __stream);
      |         ~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27