Submission #1169970

#TimeUsernameProblemLanguageResultExecution timeMemory
1169970al95ireyizLucky Numbers (RMI19_lucky)C++20
0 / 100
13 ms2372 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=1e5+5; // TEMPLATE ll n,m,k=0; inline void prc(){} vll v; ll dp[maxn][2]; #define dpp dp[l][ls] // escaping reality #define DEF -1 ll dfs(ll l, ll ls){ if(dpp != DEF) return dpp; if(l == 0) return 1; dpp = 0; for(ll i=0;i<10;i++){ if(ls and i == 3) continue; dpp += dfs(l-1, i == 1); dpp %= MOD; } return dpp; } ll get(ll a, ll b){ ll cv = 0, l = b-a, f = 0; for(ll i=a;i<=b;i++){ // i-ci index tight olmasa ne qeder kombinasiya var ? for(ll j=0;j<v[i];j++){ cv += dfs(l, j==1); cv %= MOD; } if(v[i] == 1) f = 1; else if(f and v[i] == 3) return cv; else f = 0; l --; } return (cv+1)%MOD; } void _(){ cin>>n>>m; string s; cin>>s; v.rs(n); memset(dp, DEF, sizeof(dp)); for(ll i=0;i<n;i++) v[i] = s[i] - '0'; cout<<get(0, n-1)<<'\n'; for(ll i=0,a,b,c;i<m;i++){ cin>>a>>b>>c; if(a == 1){ cout<<get(b-1, c-1)<<'\n'; } else{ v[b-1] = c; } } } 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...