oj.uz

Submission #258657

# Submission time Handle Problem Language Result Execution time Memory
258657 2020-08-06T10:31:44 Z dantoh000 Lucky Numbers (RMI19_lucky) C++14
100 / 100
 29 ms 8832 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1000000007;
ll mem[100005][2];
int a[100005];
int n,q;
ll dp(int id, int lastone){
    if (id == 0) return 1;
    if (mem[id][lastone] != -1) return mem[id][lastone];
    ll ret = 0;
    for (int i = 0; i < 10; i++){
        if (lastone && i == 3) continue;
        ret += dp(id-1,i==1);
    }
    ret %= mod;
    //printf("%d %d %lld\n",id,lastone,ret);
    return mem[id][lastone] = ret;
}
ll qu(int l, int r){
    ll ret = 0;
    int ct = r-l;
    bool isthirteenalready = false;
    for (int i = l; i <= r && !isthirteenalready; i++, ct--){
        int num = a[i]-(i!=l && a[i-1]==1 && a[i]>3);
        int numone = (a[i]>1);
        if (numone) ret += dp(ct,1);
        ret += (num-numone)*dp(ct,0);
        if (i != l && a[i-1] == 1 && a[i] == 3) isthirteenalready = true;
    }
    if (!isthirteenalready) ret++;
    ret %= mod;
    return ret;
}
int main(){
    scanf("%d%d",&n,&q);
    for (int i = 0; i < n; i++){
        char ch;
        scanf(" %c",&ch);
        a[i] = ch-'0';
    }
    memset(mem,-1,sizeof(mem));
    printf("%lld\n",qu(0,n-1));
    for (int i = 0; i < q; i++){
        int t,l,r;
        scanf("%d%d%d",&t,&l,&r);
        if (t == 1){
            printf("%lld\n",qu(--l,--r));
        }
        else{
            a[--l] = r;
        }
    }
}

Compilation message

lucky.cpp: In function 'int main()':
lucky.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&n,&q);
     ~~~~~^~~~~~~~~~~~~~
lucky.cpp:39:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %c",&ch);
         ~~~~~^~~~~~~~~~~
lucky.cpp:46:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d",&t,&l,&r);
         ~~~~~^~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2432 KB Output is correct
2 Correct 14 ms 2688 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 2432 KB Output is correct
2 Correct 14 ms 2688 KB Output is correct
3 Correct 23 ms 7296 KB Output is correct
4 Correct 24 ms 7424 KB Output is correct
5 Correct 27 ms 8184 KB Output is correct
6 Correct 29 ms 8824 KB Output is correct
7 Correct 29 ms 8824 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1920 KB Output is correct
7 Correct 10 ms 2432 KB Output is correct
8 Correct 14 ms 2688 KB Output is correct
9 Correct 7 ms 2432 KB Output is correct
10 Correct 9 ms 2560 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1920 KB Output is correct
2 Correct 1 ms 1920 KB Output is correct
3 Correct 1 ms 1920 KB Output is correct
4 Correct 1 ms 1920 KB Output is correct
5 Correct 1 ms 1920 KB Output is correct
6 Correct 1 ms 1920 KB Output is correct
7 Correct 10 ms 2432 KB Output is correct
8 Correct 14 ms 2688 KB Output is correct
9 Correct 23 ms 7296 KB Output is correct
10 Correct 24 ms 7424 KB Output is correct
11 Correct 27 ms 8184 KB Output is correct
12 Correct 29 ms 8824 KB Output is correct
13 Correct 29 ms 8824 KB Output is correct
14 Correct 7 ms 2432 KB Output is correct
15 Correct 9 ms 2560 KB Output is correct
16 Correct 21 ms 7416 KB Output is correct
17 Correct 21 ms 7424 KB Output is correct
18 Correct 25 ms 8064 KB Output is correct
19 Correct 25 ms 8832 KB Output is correct
20 Correct 26 ms 8824 KB Output is correct