제출 #443776

#제출 시각아이디문제언어결과실행 시간메모리
443776JovanBLucky Numbers (RMI19_lucky)C++17
37 / 100
397 ms122692 KiB
#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; }

컴파일 시 표준 에러 (stderr) 메시지

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 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...