Submission #1169887

#TimeUsernameProblemLanguageResultExecution timeMemory
1169887al95ireyizLucky Numbers (RMI19_lucky)C++20
28 / 100
1094 ms2504 KiB
// Sometimes we try to understand errors we shouldn't... #pragma GCC optimize("O3") #pragma GCC optimize("fast-math") #pragma GCC optimize("unroll-loops") #pragma GCC optimize("no-stack-protector") #include<bits/stdc++.h> using namespace std; // #include<ext/pb_ds/assoc_container.hpp> // #include<ext/pb_ds/tree_policy.hpp> // using namespace __gnu_pbds; // template<class T> // using Tree=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statisticslmode_update>; #if !defined(ONLINE_JUDGE) and !defined(EVAL) #include "template/debug.h" #else #define d(x...) #endif // TEMPLATE string sp=" "; #define fr first #define sc second #define in insert #define ll long long #define pb push_back #define mkp make_pair #define qll queue<ll> #define dqll deque<ll> #define mll map<ll,ll> #define vll vector<ll> #define er(x) erase(x) #define pll pair<ll,ll> #define ull unsigned ll #define mne min_element #define mxe max_element #define rs(x) resize(x) #define vpll vector<pll> #define vvll vector<vll> #define pq priority_queue #define len(x)(ll)x.size() #define lcm(x,y) x/__gcd(x,y)*y #define all(x) x.begin(),x.end() #define umll unordered_map<ll,ll> #define lg2(x)(63-__builtin_clzll(x)) #define precision(x) fixed<<setprecision(x) #define popcnt(x)(ll)__builtin_popcountll(x) template<typename t1,typename t2>istream&operator>>(istream &is,pair<t1,t2>&x){return is>>x.fr>>x.sc;} template<typename t1,typename t2>ostream&operator<<(ostream &os,pair<t1,t2>&x){return os<<x.fr<<' '<<x.sc;} template<typename t1>istream&operator>>(istream &is,vector<t1>&vc){for(t1 &j:vc)is>>j;return is;} template<typename t1>ostream&operator<<(ostream &os,vector<t1>&vc){for(t1 &j:vc)os<<j<<sp;return os;} // #define ll int_fast32_t // #define ll int_fast64_t // #pragma GCC optimize("O2") // #pragma GCC target("avx,avx2,fma") // #pragma GCC target("sse,sse2,sse3,ssse3,popcnt,abm,mmx,tune=native") const ll INF=1e9; const ll INFL=1e18; const ll MOD=1e9+7; // const ll MOD=998244353; const ll maxn=2e5+5; // TEMPLATE ll n,m,k=0; inline void prc(){} // pos, tg, ls ll dp[maxn][2][10]; #define dpp dp[pos][tg][ls] // escaping reality #define DEF -1 string q; ll dfs(ll pos, ll tg, ll ls){ if(dpp != DEF) return dpp; if(pos == len(q)){ return 1; } dpp = 0; ll lm = 9; if(tg) lm = q[pos] - '0'; for(ll i=0;i<=lm;i++){ if(ls == 1 and i == 3) continue; // 13 olmasin if(tg) dpp += dfs(pos+1, i==lm, i); else dpp += dfs(pos+1, 0, i); dpp %= MOD; } return dpp; } ll get(string s){ // memset(dp, DEF, sizeof(dp)); for(ll i=0;i<len(s)+5;i++) for(ll j=0;j<2;j++) for(ll q=0;q<10;q++) dp[i][j][q] = DEF; q = s; return dfs(0, 1, 0); } void _(){ cin>>n>>m; string s; cin>>s; cout<<get(s)<<'\n'; for(ll i=0,a,b,c;i<m;i++){ cin>>a>>b>>c; if(a == 1){ ll l = c - b + 1; cout<<get(s.substr(b-1, l))<<'\n'; } else{ s[b-1] = char('0'+c); // cout<<get(s)<<'\n'; } } } signed main(){ clock_t testcaseruntime=clock(); cin.tie(0)->sync_with_stdio(0); prc(); ll t=1; // cin>>t; for(ll tt=1;tt<=t;tt++){ // cout<<"Case "<<tt<<": "; _(); } cerr<<"\n\033[1;31mTime: \033[1;30m"<<(double)(clock()-testcaseruntime)/CLOCKS_PER_SEC<<"\033[1;32m seconds"<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...