Submission #864371

#	Time	Username	Problem	Language	Result	Execution time	Memory
864371		MinhTuan11	Lucky Numbers (RMI19_lucky)	C++17	14 / 100	7 ms	6748 KiB

lucky

#include <bits/stdc++.h>

#define int long long
#define fi first
#define se second

const int N = 2e5 + 5;
const int K = 1e2 + 5;
const int mod = 1e9 + 7;
const int inf = 1e18 + 7;

#define all(v) (v).begin(), (v).end()
#define pii pair<int, int> 

using namespace std;

mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());

int n, q;
int a[N], d[N][4];
// d[i][0/1/2/3] : numbers < 10^i (1 : first digit = 3) (2 : last digit = 1) (3 : both) 

struct node{
	
	int sum, prf, suf, bh, eq, l, r, len;
	
	// prf : first digit = 3
	// suf : last digit = 1
	// bh : both first digit = 3 and last digit = 1
	// eq : if s[l, r] lucky
	
} st[N * 4];

node merge(const node &l, const node &r){
	node cur = {0, 0, 0, 0, 0, 0, 0, 0};
	
	// update sum
	cur.sum = (cur.sum + l.sum * d[r.len][0] - l.suf * d[r.len][1] + mod * mod) % mod;
	cur.sum = (cur.sum + l.eq * r.sum - (l.eq * a[l.r] == 1) * r.prf + mod * mod) % mod;
	// cout << l.sum << ' ' << r.sum << ' ' << cur.sum << '\n';
	
	// update prf
	cur.prf = (cur.prf + l.prf * d[r.len][0] - l.bh * d[r.len][1] + mod * mod) % mod;
	cur.prf = (cur.prf + (l.eq && a[l.l] == 3) * r.sum - (l.eq && a[l.l] == 3 && a[l.r] == 1) * r.prf + mod * mod) % mod;
	
	// update suf
	cur.suf = (cur.suf + l.sum * d[r.len][2] - (l.sum * d[r.len][3]) + mod * mod) % mod;
	cur.suf = (cur.suf + (l.eq * r.suf) - (l.eq && a[l.r] == 1) * r.bh + mod * mod) % mod;
	
	// update bh
	cur.bh = (cur.bh + l.prf * d[r.len][2] - l.bh * d[r.len][3] + mod * mod) % mod;
	cur.bh = (cur.bh + (l.eq && a[l.l] == 3) * r.suf - (l.eq && a[l.l] == 3 && a[l.r] == 1) * r.bh + mod * mod) % mod;
	
	// update eq
	cur.eq = l.eq | r.eq | (!(a[l.r] == 1 && a[r.l] == 3));
	
	// update l
	cur.l = l.l;
	
	// update r
	cur.r = r.r;
	
	// update len
	cur.len = l.len + r.len;
	
	return cur;
}

void build(int id, int l, int r){
	if(l == r){
		st[id] = {a[l], (a[l] > 3), (a[l] > 1), 0, 1, l, l, 1};
		return;
	}
	int mid = l + r >> 1;
	build(id * 2, l, mid);
	build(id * 2 + 1, mid + 1, r);
	st[id] = merge(st[id * 2], st[id * 2 + 1]);
}

void update(int id, int l, int r, int pos){
	if(l > pos || r < pos) return;
	if(l == r){
		st[id] = {a[l], (a[l] > 3), (a[l] > 1), 0, 1, l, l, 1};
		return;
	}
	int mid = l + r >> 1;
	update(id * 2, l, mid, pos);
	update(id * 2 + 1, mid + 1, r, pos);
	st[id] = merge(st[id * 2], st[id * 2 + 1]);
}

node get(int id, int l, int r, int u, int v){
	if(u <= l && r <= v) return st[id];
	int mid = l + r >> 1;
	node cur = {-1, -1, -1, -1, -1, -1, -1, -1};
	if(u <= mid) cur = get(id * 2, l, mid, u, v);
	if(v > mid){
		if(cur.len == -1) cur = get(id * 2 + 1, mid + 1, r, u, v);
		else cur = merge(cur, get(id * 2 + 1, mid + 1, r, u, v));
	}
	return cur;
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    if(ifstream("file.inp")){
    	freopen("file.inp", "r", stdin);
    	freopen("file.out", "w", stdout);
    }
    
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
    	char d;
    	cin >> d;
    	a[i] = d - '0';
    }
    d[1][0] = 10, d[1][1] = 1, d[1][2] = 1, d[1][3] = 0;
    for(int i = 2; i <= n; i++){
    	d[i][0] = (d[i - 1][0] * 10 - d[i - 1][1] + mod * mod) % mod;
    	d[i][1] = d[i - 1][0];
    	d[i][2] = d[i - 1][0];
    	d[i][3] = d[i - 1][2];
    }
    build(1, 1, n);
    node fu = get(1, 1, n, 1, n);
    cout << (fu.sum + fu.eq) % mod << '\n';
    while(q--){
    	int t, x, y;
    	cin >> t >> x >> y;
    	if(t == 1){
    		node dh = get(1, 1, n, x, y);
    		cout << (dh.sum + dh.eq) % mod << '\n';
    	}
    	else{
    		a[x] = y;
    		update(1, 1, n, x);
    	}
    }
    
    return 0;
}

// tuntun

Compilation message (stderr)

lucky.cpp: In function 'void build(long long int, long long int, long long int)':
lucky.cpp:74:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   74 |  int mid = l + r >> 1;
      |            ~~^~~
lucky.cpp: In function 'void update(long long int, long long int, long long int, long long int)':
lucky.cpp:86:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   86 |  int mid = l + r >> 1;
      |            ~~^~~
lucky.cpp: In function 'node get(long long int, long long int, long long int, long long int, long long int)':
lucky.cpp:94:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |  int mid = l + r >> 1;
      |            ~~^~~
lucky.cpp: In function 'int main()':
lucky.cpp:109:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  109 |      freopen("file.inp", "r", stdin);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
lucky.cpp:110:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |      freopen("file.out", "w", stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 9
• Subtask 4: 0 / 27
• Subtask 5: 0 / 9
• Subtask 6: 0 / 27