Submission #480245

#TimeUsernameProblemLanguageResultExecution timeMemory
480245Tenis0206Lucky Numbers (RMI19_lucky)C++17
0 / 100
44 ms35552 KiB
#include <bits/stdc++.h> using namespace std; const int Mod = 1e9 + 7; struct node { int val, val1, val3, val31; int valmic, valmic1, valmic3, valmic31; bool ok, ok1, ok3, ok31; node() { val = val1 = val3 = val31 = 0; valmic = valmic1 = valmic3 = valmic31 = 0; ok = ok1 = ok3 = ok31 = false; } }; int n,q,v[100005]; node ai[1000005]; node Merge(node a, node b) { node rez; rez.val = (1LL * a.val * b.val % Mod - 1LL * a.val1 * b.val3 % Mod + Mod) % Mod; rez.val1 = (1LL * a.val * b.val1 % Mod - 1LL * a.val1 * b.val31 % Mod + Mod) % Mod; rez.val3 = (1LL * a.val3 * b.val % Mod - 1LL * a.val31 * b.val1 % Mod + Mod) % Mod; rez.val31 = (1LL * a.val3 * b.val1 % Mod - 1LL * a.val31 * b.val31 % Mod + Mod) % Mod; rez.valmic = ((1LL * a.valmic * b.val % Mod - 1LL * a.valmic1 * b.val3 % Mod + Mod) % Mod + (1LL * a.ok * b.valmic % Mod - 1LL * a.ok1 * b.valmic3 % Mod + Mod)) % Mod; rez.valmic1 = ((1LL * a.valmic * b.val1 % Mod - 1LL * a.valmic1 * b.val31 % Mod + Mod) % Mod + (1LL * a.ok * b.valmic1 % Mod - 1LL * a.ok1 * b.valmic31 % Mod + Mod)) % Mod; rez.valmic3 = ((1LL * a.valmic3 * b.val % Mod - 1LL * a.valmic31 * b.val3 % Mod + Mod) % Mod + (1LL * a.ok3 * b.valmic % Mod - 1LL * a.ok31 * b.valmic1 % Mod + Mod)) % Mod; rez.valmic31 = ((1LL * a.valmic3 * b.val1 % Mod - 1LL * a.valmic31 * b.val31 % Mod + Mod) % Mod + (1LL * a.ok3 * b.valmic1 % Mod - 1LL * a.ok31 * b.valmic31 % Mod + Mod)) % Mod; rez.ok = (a.ok & b.ok & ((!a.ok1)|(!b.ok3))); rez.ok1 = (rez.ok & a.ok1); rez.ok3 = (rez.ok & b.ok3); rez.ok31 = (rez.ok & a.ok1 & b.ok3); return rez; } node Init(int val) { node rez; rez.val = 10; rez.val1 = 1; rez.val3 = 1; rez.val31 = 0; rez.valmic = val; rez.valmic1 = (1<val); rez.valmic3 = (3<val); rez.valmic31 = 0; rez.ok = true; rez.ok1 = (val==1); rez.ok3 = (val==3); rez.ok31 = false; return rez; } void update(int poz, int val, int nod, int a, int b) { if(a==b) { ai[nod] = Init(val); return; } int mij = (a+b)>>1; if(poz<=mij) { update(poz,val,nod*2,a,mij); } else { update(poz,val,nod*2+1,mij+1,b); } ai[nod] = Merge(ai[nod*2],ai[nod*2+1]); } node query(int qa, int qb, int nod, int a, int b) { if(qa<=a && qb>=b) { return ai[nod]; } int mij = (a+b)>>1; node rez1, rez2; if(qa<=mij) { rez1 = query(qa,qb,nod*2,a,mij); } if(qb>mij) { rez2 = query(qa,qb,nod*2+1,mij+1,b); } if(qa<=mij && qb<=mij) { return rez1; } if(qa>mij && qb>mij) { return rez2; } return Merge(rez1,rez2); } int main() { ios::sync_with_stdio(false); cin.tie(0); // freopen("nr.in","r",stdin); // freopen("nr.out","w",stdout); cin>>n>>q; cin.get(); for(int i=1;i<=n;i++) { char ch; cin.get(ch); v[i] = ch - '0'; update(i,v[i],1,1,n); } node rez = query(1,n,1,1,n); cout<<rez.valmic + rez.ok<<'\n'; for(int i=1;i<=q;i++) { int t; cin>>t; if(t==1) { int l,r; cin>>l>>r; node rez = query(l,r,1,1,n); cout<<rez.valmic + rez.ok<<'\n'; } else { int poz,val; cin>>poz>>val; update(poz,val,1,1,n); } } return 0; }
#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...