Submission #532149

#TimeUsernameProblemLanguageResultExecution timeMemory
532149i_am_noobLucky Numbers (RMI19_lucky)C++17
28 / 100
9 ms2644 KiB
#include <bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast,unroll-loops") #define ll long long #define int ll #define ull unsigned ll #define ld long double #define rep(a) rep1(i,a) #define rep1(i,a) rep2(i,0,a) #define rep2(i,b,a) for(int i=(b); i<((int)(a)); i++) #define rep3(i,b,a) for(int i=(b); i>=((int)(a)); i--) #define chkmin(a,b) (a=min(a,b)) #define chkmax(a,b) (a=max(a,b)) #define all(a) a.begin(),a.end() #define pii pair<int,int> #define pb push_back //#define inf 1010000000 #define inf 4000000000000000000 #define eps 1e-9 #define sz(a) ((int)a.size()) #define pow2(x) (1ll<<(x)) #define ceiling(a,b) (((a)+(b)-1)/(b)) #define print0(a) cout << (a) << ' ' #define ykh mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()) #ifdef i_am_noob #define bug(...) cerr << "#" << __LINE__ << ' ' << #__VA_ARGS__ << "- ", _do(__VA_ARGS__) template<typename T> void _do(T && x) {cerr << x << endl;} template<typename T, typename ...S> void _do(T && x, S&&...y) {cerr << x << ", "; _do(y...);} #else #define bug(...) 777771449 #endif const int mod=1000000007; const int maxn=10005,maxm=5,maxk=7777714; //i_am_noob int dp[maxn][2],dp2[maxn][2];//0: ends with anything but 3, 1: ends with 3 struct obj{ int len;//length of the number int val0,val1;//# of ways end with {not 1, 1} bool good;//does not contain "13" int begin,end;//first digit, last digit obj(){len=0;} void set(int x){ len=1; if(x>1) val1=1; else val1=0; val0=x-val1; good=1; begin=end=x; } }; obj Merge(obj x, obj y){ if(x.len==0) return y; if(y.len==0) return x; obj res; res.len=x.len+y.len; res.good=1; if(x.end==1&&y.begin==3) res.good=0; if((!x.good)&&(!y.good)) res.good=0; res.begin=x.begin; res.end=y.end; res.val0=res.val1=0; res.val0+=(dp[y.len][0]*8+dp[y.len][1])%mod*x.val0+(dp2[y.len][0]*8+dp2[y.len][1])%mod*x.val1; res.val0%=mod; res.val1+=dp[y.len][0]*x.val0+dp2[y.len][0]*x.val1; res.val1%=mod; if(!x.good){} else if(x.end!=1){ res.val0+=y.val0; res.val0%=mod; res.val1+=y.val1; res.val1%=mod; } else if(y.begin!=3){ res.val0+=y.val0; res.val0%=mod; res.val1+=y.val1; res.val1%=mod; if(y.begin>3){ if(y.len==1){ res.val0--; if(res.val0<0) res.val0+=mod; } else{ res.val0-=(dp[y.len-1][0]*8+dp[y.len-1][1])%mod; res.val0+=mod; res.val0%=mod; res.val1-=dp[y.len-1][0]; res.val1+=mod; res.val1%=mod; } } } else{ if(y.len==1){ res.val0+=3; res.val0%=mod; res.val1++; res.val1%=mod; } else{ res.val0+=(dp[y.len-1][0]*8+dp[y.len-1][1])*3+(dp2[y.len-1][0]*8+dp2[y.len-1][1]); res.val0%=mod; res.val1+=(dp[y.len-1][0])*3+dp2[y.len-1][0]; res.val1%=mod; } } return res; } obj node[maxn*4]; int n,q; string str; void pull(int k){node[k]=Merge(node[k<<1],node[k<<1|1]);} void build(int k, int l, int r){ if(l==r){ node[k].set(str[l]-'0'); return; } int mid=l+r>>1; build(k<<1,l,mid),build(k<<1|1,mid+1,r); pull(k); } void modify(int k, int l, int r, int p, int x){ if(l==r){ node[k].set(x); return; } int mid=l+r>>1; if(p<=mid) modify(k<<1,l,mid,p,x); else modify(k<<1|1,mid+1,r,p,x); pull(k); } obj query(int k, int l, int r, int ql, int qr){ if(l>qr||r<ql) return obj(); if(ql<=l&&qr>=r){ return node[k]; } int mid=l+r>>1; return Merge(query(k<<1,l,mid,ql,qr),query(k<<1|1,mid+1,r,ql,qr)); } int query(int l, int r){ obj res=query(1,0,n-1,l,r); int tot=res.val0+res.val1; if(res.good) tot++; tot+=mod; tot%=mod; return tot; } void orzck(){ dp[1][0]=dp[1][1]=1; rep2(i,2,maxn) dp[i][0]=(dp[i-1][0]*9+dp[i-1][1])%mod,dp[i][1]=(dp[i-1][0]*8+dp[i-1][1])%mod; dp2[1][0]=1,dp2[1][1]=0; rep2(i,2,maxn) dp2[i][0]=(dp2[i-1][0]*9+dp2[i-1][1])%mod,dp2[i][1]=(dp2[i-1][0]*8+dp2[i-1][1])%mod; cin >> n >> q >> str; build(1,0,n-1); cout << query(0,n-1) << "\n"; while(q--){ int op; cin >> op; if(op==1){ int l,r; cin >> l >> r; l--,r--; cout << query(l,r) << "\n"; } else{ int p,x; cin >> p >> x; p--; modify(1,0,n-1,p,x); } } } signed main(){ ios_base::sync_with_stdio(0),cin.tie(0); orzck(); return 0; }

Compilation message (stderr)

lucky.cpp: In function 'void build(long long int, long long int, long long int)':
lucky.cpp:116:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  116 |     int mid=l+r>>1;
      |             ~^~
lucky.cpp: In function 'void modify(long long int, long long int, long long int, long long int, long long int)':
lucky.cpp:126:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  126 |     int mid=l+r>>1;
      |             ~^~
lucky.cpp: In function 'obj query(long long int, long long int, long long int, long long int, long long int)':
lucky.cpp:137:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  137 |     int mid=l+r>>1;
      |             ~^~
#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...