oj.uz

Submission #331816

# Submission time Handle Problem Language Result Execution time Memory
331816 2020-11-30T09:22:46 Z Ruxandra985 Lucky Numbers (RMI19_lucky) C++14
100 / 100
 183 ms 25452 KB 
/**
* 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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2020 KB Output is correct
2 Correct 81 ms 3564 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 2020 KB Output is correct
2 Correct 81 ms 3564 KB Output is correct
3 Correct 142 ms 25344 KB Output is correct
4 Correct 142 ms 25324 KB Output is correct
5 Correct 153 ms 25324 KB Output is correct
6 Correct 171 ms 25324 KB Output is correct
7 Correct 183 ms 25324 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 60 ms 2020 KB Output is correct
8 Correct 81 ms 3564 KB Output is correct
9 Correct 66 ms 2048 KB Output is correct
10 Correct 85 ms 3564 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 60 ms 2020 KB Output is correct
8 Correct 81 ms 3564 KB Output is correct
9 Correct 142 ms 25344 KB Output is correct
10 Correct 142 ms 25324 KB Output is correct
11 Correct 153 ms 25324 KB Output is correct
12 Correct 171 ms 25324 KB Output is correct
13 Correct 183 ms 25324 KB Output is correct
14 Correct 66 ms 2048 KB Output is correct
15 Correct 85 ms 3564 KB Output is correct
16 Correct 143 ms 25324 KB Output is correct
17 Correct 171 ms 25196 KB Output is correct
18 Correct 180 ms 25324 KB Output is correct
19 Correct 176 ms 25324 KB Output is correct
20 Correct 181 ms 25452 KB Output is correct