#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int MOD = 1000000007;
int add(int a, int b){ a += b; if(a >= MOD) a -= MOD; return a; }
int mul(int a, int b){ return (1LL*a*b)%MOD; }
int seg[400500][5][5][5];
void clr(int node){
for(int i=0; i<=2; i++) for(int j=1; j<=3; j++) for(int k=1; k<=3; k++) seg[node][i][j][k] = 0;
}
void cpy(int node, int pnode){
for(int i=0; i<=2; i++) for(int j=1; j<=3; j++) for(int k=1; k<=3; k++) seg[node][i][j][k] = seg[pnode][i][j][k];
}
void mrg(int nnode, int a, int b){
for(int i=1; i<=3; i++){
for(int j=1; j<=3; j++){
seg[nnode][0][i][j] = seg[nnode][1][i][j] = seg[nnode][2][i][j] = 0;
for(int k=1; k<=3; k++){
for(int g=1; g<=3; g++){
if(k == 1 && g == 3) continue;
seg[nnode][0][i][j] = add(seg[nnode][0][i][j], mul(seg[a][0][i][k], add(seg[b][0][g][j], add(seg[b][1][g][j], seg[b][2][g][j]))));
seg[nnode][2][i][j] = add(seg[nnode][2][i][j], mul(seg[a][2][i][k], add(seg[b][0][g][j], add(seg[b][1][g][j], seg[b][2][g][j]))));
for(int d=0; d<=2; d++) seg[nnode][d][i][j] = add(seg[nnode][d][i][j], mul(seg[a][1][i][k], seg[b][d][g][j]));
}
}
}
}
}
vector <int> nodes;
string s;
void init(int node, int l, int r){
if(l == r){
int d = s[l-1] - '0';
for(int i=0; i<10; i++){
int c;
if(i < d) c = 0;
else if(i == d) c = 1;
else c = 2;
if(i == 1) seg[node][c][1][1]++;
else if(i == 3) seg[node][c][3][3]++;
else seg[node][c][2][2]++;
}
return;
}
int mid = (l+r)/2;
init(node*2, l, mid);
init(node*2+1, mid+1, r);
mrg(node, node*2, node*2+1);
}
void upd(int node, int l, int r, int x){
if(l == r){
clr(node);
int d = s[l-1] - '0';
for(int i=0; i<10; i++){
int c;
if(i < d) c = 0;
else if(i == d) c = 1;
else c = 2;
if(i == 1) seg[node][c][1][1]++;
else if(i == 3) seg[node][c][3][3]++;
else seg[node][c][2][2]++;
}
return;
}
int mid = (l+r)/2;
if(x <= mid) upd(node*2, l, mid, x);
else upd(node*2+1, mid+1, r, x);
mrg(node, node*2, node*2+1);
}
void query(int node, int l, int r, int tl, int tr){
if(tl > r || l > tr) return;
if(tl <= l && r <= tr){
nodes.push_back(node);
return;
}
int mid = (l+r)/2;
query(node*2, l, mid, tl, tr);
query(node*2+1, mid+1, r, tl, tr);
}
int main(){
ios_base::sync_with_stdio(false), cin.tie(0);
cout.precision(10);
cout << fixed;
int n, qrs;
cin >> n >> qrs;
cin >> s;
init(1, 1, n);
int dm = 4*n+1;
cpy(dm, 1);
int res = 0;
for(int i=1; i<=3; i++) for(int j=1; j<=3; j++) res = add(res, add(seg[dm][0][i][j], seg[dm][1][i][j]));
cout << res << "\n";
while(qrs--){
int typ;
cin >> typ;
if(typ == 1){
nodes.clear();
int l, r;
cin >> l >> r;
clr(dm);
query(1, 1, n, l, r);
cpy(dm, nodes[0]);
assert(nodes.size() <= 60);
for(int i=1; i<nodes.size(); i++){
mrg(dm+i, dm+i-1, nodes[i]);
}
int x = dm+nodes.size()-1;
res = 0;
for(int i=1; i<=3; i++) for(int j=1; j<=3; j++) res = add(res, add(seg[x][0][i][j], seg[x][1][i][j]));
cout << res << "\n";
}
else{
int a;
char b;
cin >> a >> b;
s[a-1] = b;
upd(1, 1, n, a);
}
}
return 0;
}
Compilation message
lucky.cpp: In function 'int main()':
lucky.cpp:119:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
119 | for(int i=1; i<nodes.size(); i++){
| ~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
8356 KB |
Output is correct |
| 2 |
Correct |
191 ms |
15672 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
143 ms |
8356 KB |
Output is correct |
| 2 |
Correct |
191 ms |
15672 KB |
Output is correct |
| 3 |
Execution timed out |
397 ms |
122692 KB |
Time limit exceeded |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
143 ms |
8356 KB |
Output is correct |
| 8 |
Correct |
191 ms |
15672 KB |
Output is correct |
| 9 |
Correct |
163 ms |
8340 KB |
Output is correct |
| 10 |
Execution timed out |
209 ms |
15640 KB |
Time limit exceeded |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
0 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Correct |
0 ms |
204 KB |
Output is correct |
| 5 |
Correct |
1 ms |
332 KB |
Output is correct |
| 6 |
Correct |
1 ms |
332 KB |
Output is correct |
| 7 |
Correct |
143 ms |
8356 KB |
Output is correct |
| 8 |
Correct |
191 ms |
15672 KB |
Output is correct |
| 9 |
Execution timed out |
397 ms |
122692 KB |
Time limit exceeded |
| 10 |
Halted |
0 ms |
0 KB |
- |
