Submission #200648

#TimeUsernameProblemLanguageResultExecution timeMemory
200648nicolaalexandraLucky Numbers (RMI19_lucky)C++14
28 / 100
39 ms2172 KiB
#include <bits/stdc++.h> #define DIM 100010 #define MOD 1000000007 using namespace std; int v[DIM]; int n,q,c,x,y,i,_first; long long sol0,sol1,sol3,sol_fin0,sol_fin1,sol_fin3; char ch; struct segment_tree{ long long s00, s01, s03; long long s10, s11, s13; long long s30, s31, s33; }; segment_tree aint[DIM*4], dp[DIM]; void update_node (int nod, int st, int dr){ int fiu_st = nod<<1, fiu_dr = (nod<<1)|1; if (dr - st == 1){ aint[nod].s00 = 1LL*aint[fiu_st].s00 * dp[1].s00 % MOD; aint[nod].s01 = 1LL*aint[fiu_st].s00 * dp[1].s11 % MOD; aint[nod].s03 = 1LL*aint[fiu_st].s00 * dp[1].s33 % MOD; if (v[st] != 1 && v[st] != 3){ aint[nod].s00 = (aint[nod].s00 + aint[fiu_dr].s00) % MOD; aint[nod].s01 = (aint[nod].s01 + aint[fiu_dr].s11) % MOD; aint[nod].s03 = (aint[nod].s03 + aint[fiu_dr].s33) % MOD; } aint[nod].s10 = 1LL * aint[fiu_st].s11 * dp[1].s00 % MOD; aint[nod].s11 = 1LL * aint[fiu_st].s11 * dp[1].s11 % MOD; if (v[st] == 1){ aint[nod].s10 = (aint[nod].s10 + aint[fiu_dr].s00) % MOD; aint[nod].s11 = (aint[nod].s11 + aint[fiu_dr].s11) % MOD; } aint[nod].s13 = 0; aint[nod].s30 = 1LL*aint[fiu_st].s33 * dp[1].s00 % MOD; aint[nod].s31 = 1LL*aint[fiu_st].s33 * dp[1].s11 % MOD; aint[nod].s33 = 1LL*aint[fiu_st].s33 * dp[1].s33 % MOD; if (v[st] == 3){ aint[nod].s30 = (aint[nod].s30 + aint[fiu_dr].s00) % MOD; aint[nod].s31 = (aint[nod].s31 + aint[fiu_dr].s11) % MOD; aint[nod].s33 = (aint[nod].s33 + aint[fiu_dr].s33) % MOD; } return; } int mid = (st+dr)>>1; int nr = dr-mid; /// stare 00 long long sum = 0; sum = (sum + dp[nr].s00) % MOD; sum = (sum + dp[nr].s10) % MOD; sum = (sum + dp[nr].s30) % MOD; aint[nod].s00 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD; aint[nod].s00 = (aint[nod].s00 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD; /// la cazul asta nu am voie cu 3 long long val = sum - dp[nr].s30; if (val < 0) val += MOD; aint[nod].s00 = (aint[nod].s00 + 1LL*aint[fiu_st].s01*val % MOD) % MOD; /// stare 01 sum = 0; sum = (sum + dp[nr].s01) % MOD; sum = (sum + dp[nr].s11) % MOD; sum = (sum + dp[nr].s31) % MOD; aint[nod].s01 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD; aint[nod].s01 = (aint[nod].s01 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD; val = sum - dp[nr].s31; if (val < 0) val += MOD; aint[nod].s01 = (aint[nod].s01 + 1LL*aint[fiu_st].s01*val % MOD) % MOD; /// stare 03 sum = 0; sum = (sum + dp[nr].s03) % MOD; sum = (sum + dp[nr].s13) % MOD; sum = (sum + dp[nr].s33) % MOD; aint[nod].s03 = (1LL*aint[fiu_st].s00*sum % MOD) % MOD; aint[nod].s03 = (aint[nod].s03 + 1LL*aint[fiu_st].s03*sum % MOD) % MOD; val = sum - dp[nr].s33; if (val < 0) val += MOD; aint[nod].s03 = (aint[nod].s03 + 1LL*aint[fiu_st].s01*val % MOD) % MOD; /// stare 10 sum = 0; sum = (sum + dp[nr].s00) % MOD; sum = (sum + dp[nr].s10) % MOD; sum = (sum + dp[nr].s30) % MOD; aint[nod].s10 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD; aint[nod].s10 = (aint[nod].s10 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD; val = sum - dp[nr].s30; if (val < 0) val += MOD; aint[nod].s10 = (aint[nod].s10 + 1LL*aint[fiu_st].s11*val%MOD) % MOD; /// stare 11 sum = 0; sum = (sum + dp[nr].s01) % MOD; sum = (sum + dp[nr].s11) % MOD; sum = (sum + dp[nr].s31) % MOD; aint[nod].s11 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD; aint[nod].s11 = (aint[nod].s11 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD; val = sum - dp[nr].s31; if (val < 0) val += MOD; aint[nod].s11 = (aint[nod].s11 + 1LL*aint[fiu_st].s11*val%MOD) % MOD; /// stare 13 sum = 0; sum = (sum + dp[nr].s03) % MOD; sum = (sum + dp[nr].s13) % MOD; sum = (sum + dp[nr].s33) % MOD; aint[nod].s13 = (1LL*aint[fiu_st].s10*sum%MOD) % MOD; aint[nod].s13 = (aint[nod].s13 + 1LL*aint[fiu_st].s13*sum%MOD) % MOD; val = sum - dp[nr].s33; if (val < 0) val += MOD; aint[nod].s13 = (aint[nod].s13 + 1LL*aint[fiu_st].s11*val%MOD) % MOD; /// stare 30 sum = 0; sum = (sum + dp[nr].s00) % MOD; sum = (sum + dp[nr].s10) % MOD; sum = (sum + dp[nr].s30) % MOD; aint[nod].s30 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD; aint[nod].s30 = (aint[nod].s30 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD; val = sum - dp[nr].s30; if (val < 0) val += MOD; aint[nod].s30 = (aint[nod].s30 + 1LL*aint[fiu_st].s31*val%MOD) % MOD; /// stare 31 sum = 0; sum = (sum + dp[nr].s01) % MOD; sum = (sum + dp[nr].s11) % MOD; sum = (sum + dp[nr].s31) % MOD; aint[nod].s31 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD; aint[nod].s31 = (aint[nod].s31 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD; val = sum - dp[nr].s31; if (val < 0) val += MOD; aint[nod].s31 = (aint[nod].s31 + 1LL*aint[fiu_st].s31*val%MOD) % MOD; /// stare 33 sum = 0; sum = (sum + dp[nr].s03) % MOD; sum = (sum + dp[nr].s13) % MOD; sum = (sum + dp[nr].s33) % MOD; aint[nod].s33 = (1LL*aint[fiu_st].s30*sum%MOD) % MOD; aint[nod].s33 = (aint[nod].s33 + 1LL*aint[fiu_st].s33*sum%MOD) % MOD; val = sum - dp[nr].s33; if (val < 0) val += MOD; aint[nod].s33 = (aint[nod].s33 + 1LL*aint[fiu_st].s31*val%MOD) % MOD; /// acum mai ramane cazul in care pastrez fiul stang integral asa cum e si /// trebuie sa adaug de la fiul drept pt toate starile /// singurul caz special e cand am pe mid 1 sum = (aint[fiu_dr].s00 + aint[fiu_dr].s01 + aint[fiu_dr].s03) % MOD; sum = (sum + aint[fiu_dr].s10 + aint[fiu_dr].s11 + aint[fiu_dr].s13) % MOD; sum = (sum + aint[fiu_dr].s30 + aint[fiu_dr].s31 + aint[fiu_dr].s33) % MOD; if (v[st] == 1){ aint[nod].s10 = (aint[nod].s10 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD; aint[nod].s11 = (aint[nod].s11 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD; aint[nod].s13 = (aint[nod].s13 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD; if (v[mid] == 1){ /// trebuie sa mai scad cv aint[nod].s10 -= aint[fiu_dr].s30; if (aint[nod].s10 < 0) aint[nod].s10 += MOD; aint[nod].s11 -= aint[fiu_dr].s31; if (aint[nod].s11 < 0) aint[nod].s11 += MOD; aint[nod].s13 -= aint[fiu_dr].s33; if (aint[nod].s13 < 0) aint[nod].s13 += MOD; } } else { if (v[st] == 3){ aint[nod].s30 = (aint[nod].s30 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD; aint[nod].s31 = (aint[nod].s31 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD; aint[nod].s33 = (aint[nod].s33 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD; if (v[mid] == 1){ /// trebuie sa mai scad cv aint[nod].s30 -= aint[fiu_dr].s30; if (aint[nod].s30 < 0) aint[nod].s30 += MOD; aint[nod].s31 -= aint[fiu_dr].s31; if (aint[nod].s31 < 0) aint[nod].s31 += MOD; aint[nod].s33 -= aint[fiu_dr].s33; if (aint[nod].s33 < 0) aint[nod].s33 += MOD; } } else { /// altceva => 0 aint[nod].s00 = (aint[nod].s00 + aint[fiu_dr].s00 + aint[fiu_dr].s10 + aint[fiu_dr].s30) % MOD; aint[nod].s01 = (aint[nod].s01 + aint[fiu_dr].s01 + aint[fiu_dr].s11 + aint[fiu_dr].s31) % MOD; aint[nod].s03 = (aint[nod].s03 + aint[fiu_dr].s03 + aint[fiu_dr].s13 + aint[fiu_dr].s33) % MOD; if (v[mid] == 1){ /// trebuie sa mai scad cv aint[nod].s00 -= aint[fiu_dr].s30; if (aint[nod].s00 < 0) aint[nod].s00 += MOD; aint[nod].s01 -= aint[fiu_dr].s31; if (aint[nod].s01 < 0) aint[nod].s01 += MOD; aint[nod].s03 -= aint[fiu_dr].s33; if (aint[nod].s03 < 0) aint[nod].s03 += MOD; }}}} void build (int nod, int st, int dr){ if (st == dr){ if (v[st] == 0) return; if (v[st] == 1){ aint[nod].s00 = 1; return; } if (v[st] == 2){ aint[nod].s00 = 1, aint[nod].s11 = 1; return; } if (v[st] == 3){ aint[nod].s00 = 2, aint[nod].s11 = 1; return; } aint[nod].s11 = aint[nod].s33 = 1; aint[nod].s00 = v[st] - 2; return; } int mid = (st+dr)>>1; build (nod<<1,st,mid); build ((nod<<1)|1,mid+1,dr); update_node (nod,st,dr); } void update (int nod, int st, int dr, int poz, int val){ if (st == dr){ aint[nod].s00 = aint[nod].s11 = aint[nod].s33 = 0; if (val == 0) return; if (val == 1){ aint[nod].s00 = 1; return; } if (val == 2){ aint[nod].s00 = 1, aint[nod].s11 = 1; return; } if (val == 3){ aint[nod].s00 = 2, aint[nod].s11 = 1; return; } aint[nod].s11 = aint[nod].s33 = 1; aint[nod].s00 = val - 2; return; } int mid = (st+dr)>>1; if (poz <= mid) update (nod<<1,st,mid,poz,val); else update ((nod<<1)|1,mid+1,dr,poz,val); update_node (nod,st,dr); } void query (int nod, int st, int dr, int x, int y){ if (x <= st && dr <= y){ /// vreau sa adaug intervalul asta la solutie long long sol_aux0 = 0, sol_aux1 = 0, sol_aux3 = 0; int nr = dr-st+1; /// cate am dupa /// daca iau toate nr din intervalul asta mai mici, restul le completez cu dp if (!_first){ _first = 1; sol0 = (aint[nod].s00 + aint[nod].s10 + aint[nod].s30)%MOD; sol1 = (aint[nod].s01 + aint[nod].s11 + aint[nod].s31)%MOD; sol3 = (aint[nod].s03 + aint[nod].s13 + aint[nod].s33)%MOD; sol_aux0 = sol0, sol_aux1 = sol1, sol_aux3 = sol3; } else { /// sol_aux0 long long sum = (dp[nr].s00 + dp[nr].s10 + dp[nr].s30) % MOD; sol_aux0 = (sol_aux0 + sol0 * sum % MOD) % MOD; sol_aux0 = (sol_aux0 + sol3 * sum % MOD) % MOD; sum -= dp[nr].s30; if (sum < 0) sum += MOD; sol_aux0 = (sol_aux0 + sol1 * sum % MOD) % MOD; /// sol_aux 1 sum = (dp[nr].s01 + dp[nr].s11 + dp[nr].s31) % MOD; sol_aux1 = (sol_aux1 + sol0 * sum % MOD) % MOD; sol_aux1 = (sol_aux1 + sol3 * sum % MOD) % MOD; sum -= dp[nr].s31; if (sum < 0) sum += MOD; sol_aux1 = (sol_aux1 + sol1 * sum % MOD) % MOD; /// sol_aux3 sum = (dp[nr].s03 + dp[nr].s13 + dp[nr].s33) % MOD; sol_aux3 = (sol_aux3 + sol0 * sum % MOD) % MOD; sol_aux3 = (sol_aux3 + sol3 * sum % MOD) % MOD; sum -= dp[nr].s33; if (sum < 0) sum += MOD; sol_aux3 = (sol_aux3 + sol1 * sum % MOD) % MOD; /// cazul cu egalitatatea -> trb sa iau doar valorile mai mici din intv asta sum = (aint[nod].s00 + aint[nod].s10 + aint[nod].s30) % MOD; if (v[st-1] == 1){ sum -= aint[nod].s30; if (sum < 0) sum += MOD; sol_aux0 = (sol_aux0 + sum) % MOD; } else sol_aux0 = (sol_aux0 + sum) % MOD; /// sum = (aint[nod].s01 + aint[nod].s11 + aint[nod].s31) % MOD; if (v[st-1] == 1){ sum -= aint[nod].s31; if (sum < 0) sum += MOD; sol_aux1 = (sol_aux1 + sum) % MOD; } else sol_aux1 = (sol_aux1 + sum) % MOD; /// sum = (aint[nod].s03 + aint[nod].s13 + aint[nod].s33) % MOD; if (v[st-1] == 1){ sum -= aint[nod].s33; if (sum < 0) sum += MOD; sol_aux3 = (sol_aux3 + sum) % MOD; } else sol_aux3 = (sol_aux3 + sum) % MOD; } sol0 = sol_aux0; sol1 = sol_aux1; sol3 = sol_aux3; return; } int mid = (st+dr)>>1; if (x <= mid) query (nod<<1,st,mid,x,y); if (y > mid) query ((nod<<1)|1,mid+1,dr,x,y); } int main (){ //ifstream cin ("date.in"); //ofstream cout ("date.out"); cin>>n>>q; for (i=1;i<=n;i++){ cin>>ch; v[i] = ch - '0'; } /// dp[i].stare - cate nr de i cifre pot forma care au starea stare dp[1].s11 = dp[1].s33 = 1; dp[1].s00 = 8; for (i=2;i<=n;i++){ dp[i].s00 = 8 * (dp[i-1].s00 + dp[i-1].s01 + dp[i-1].s03) % MOD; dp[i].s01 = (dp[i-1].s00 + dp[i-1].s01 + dp[i-1].s03) % MOD; dp[i].s03 = (dp[i-1].s00 + dp[i-1].s03) % MOD; dp[i].s10 = 8 * (dp[i-1].s10 + dp[i-1].s11 + dp[i-1].s13) % MOD; dp[i].s11 = (dp[i-1].s10 + dp[i-1].s11 + dp[i-1].s13) % MOD; dp[i].s13 = (dp[i-1].s10 + dp[i-1].s13) % MOD; dp[i].s30 = 8 * (dp[i-1].s30 + dp[i-1].s31 + dp[i-1].s33) % MOD; dp[i].s31 = (dp[i-1].s30 + dp[i-1].s31 + dp[i-1].s33) % MOD; dp[i].s33 = (dp[i-1].s30 + dp[i-1].s33) % MOD; } build (1,1,n); sol0 = sol1 = sol3 = _first = 0; query(1,1,n,1,n); cout<<(sol0 + sol1 + sol3 + 1)%MOD<<"\n"; /// aint[nod] - cate nr mai mici sau egale decat intervalul ala pot forma for (;q--;){ cin>>c>>x>>y; if (c == 1){ /// query sol0 = sol1 = sol3 = _first = 0; query (1,1,n,x,y); int sol = (sol0 + sol1 + sol3 + 1) % MOD; cout<<sol<<"\n"; } else { v[x] = y; update (1,1,n,x,y); } } 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...