이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 sub(int a, int b){ return add(a, MOD-b); }
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];
}
int L[5][5], R[5][5];
void mrg(int nnode, int a, int b){
for(int i=1; i<=3; i++){
for(int p=0; p<=2; p++) L[p][i] = 0;
for(int f=1; f<=3; f++){
for(int p=0; p<=2; p++) L[p][i] = add(L[p][i], seg[a][p][i][f]);
}
}
for(int i=1; i<=3; i++){
for(int p=0; p<=2; p++) R[p][i] = 0;
for(int f=1; f<=3; f++){
for(int p=0; p<=2; p++) R[p][i] = add(R[p][i], seg[b][p][f][i]);
}
}
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;
seg[nnode][0][i][j] = add(seg[nnode][0][i][j], mul(L[0][i], add(R[0][j], add(R[1][j], R[2][j]))));
seg[nnode][2][i][j] = add(seg[nnode][2][i][j], mul(L[2][i], add(R[0][j], add(R[1][j], R[2][j]))));
for(int d=0; d<=2; d++) seg[nnode][d][i][j] = add(seg[nnode][d][i][j], mul(L[1][i], R[d][j]));
for(int k=1; k<=1; k++){
for(int g=3; g<=3; g++){
seg[nnode][0][i][j] = sub(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] = sub(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] = sub(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;
}
컴파일 시 표준 에러 (stderr) 메시지
lucky.cpp: In function 'int main()':
lucky.cpp:136:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
136 | for(int i=1; i<nodes.size(); i++){
| ~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |