This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define EQ 0
#define LE 1
using namespace std;
const int NMAX = 1e4+2;
const int SIGMA = 10;
int n,q,t,l,r,pos,val,dp[2][SIGMA][NMAX];
string s;
int countWays(string str){
memset(dp, 0, sizeof(dp));
dp[EQ][0][0] = 1;
for(int i = 1; i < str.size(); i++){
for(auto state : {EQ, LE}){
if(state == EQ){
for(int dig = 0; dig <= 9; dig++){
if(dig < str[i]-'0'){
/// LE
for(int lst = 0; lst <= 9; lst++){
if(lst == 1 && dig == 3){
continue;
}
dp[LE][dig][i] += dp[EQ][lst][i-1];
}
}else if(dig == str[i]-'0'){
/// EQ
for(int lst = 0; lst <= 9; lst++){
if(lst == 1 && dig == 3){
continue;
}
dp[EQ][dig][i] += dp[EQ][lst][i-1];
}
}
}
}else{
for(int dig = 0; dig <= 9; dig++){
for(int lst = 0; lst <= 9; lst++){
if(lst == 1 && dig == 3){
continue;
}
dp[LE][dig][i] += dp[LE][lst][i-1];
}
}
}
}
}
int ans = 0;
for(int i = 0; i <= 9; i++){
ans += dp[LE][i][str.size()-1] + dp[EQ][i][str.size()-1];
}
return ans;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> q;
cin >> s;
s = "$"+s;
cout << countWays(s) << "\n";
while(q--){
cin >> t;
if(t == 1){
cin >> l >> r;
int len = r-l+1;
string str = s.substr(l, len);
cout << countWays("$"+str) << "\n";
}else{
cin >> pos >> val;
s[pos] = (val+'0');
}
}
return 0;
}
Compilation message (stderr)
lucky.cpp: In function 'int countWays(std::string)':
lucky.cpp:13:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
13 | for(int i = 1; i < str.size(); i++){
| ~~^~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |