Submission #198082

#	Time	Username	Problem	Language	Result	Execution time	Memory
198082		model_code	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	133 ms	11548 KiB

lucky

/**
* user:  lifar-7f1
* fname: Egor
* lname: Lifar
* task:  lucky
* score: 100.0
* date:  2019-10-10 06:24:48.457257
*/
#include <bits/stdc++.h>

using namespace std;
template<class A, class B> inline void chkmin(A &a, B b){ a = (a > b ? b: a);}
template<class A, class B> inline void chkmax(A &a, B b){ a = (a < b ? b: a);}
#define all(c) (c).begin(), (c).end()
#define sz(c) (int)(c).size()
#define pb push_back
#define mp make_pair
using ll = long long;
using ld = long double;
const int MAXN = 100001;
const int Mod = 1000000007;
const int res = 400000;

int sum(const int a, const int b) {
	return (a + b >= Mod ? a + b - Mod: a + b);
}

int mul(const int a, const int b) {
	return ((ll)a * b) % Mod;
}


//0, 1 - first digit is 3 or not
//0, 1 - last digit is 1 or not
//0, 1, 2 - type of number
// 0  < x
// 1 = x
// 2 > x


int n, q;
string x;
int dp[MAXN * 4][2][2][3];
int ss = 1;


inline int get(const int x, const int y) {
	if (x < y) {
		return 0;
	}
	if (x == y) {
		return 1;
	}
	return 2;
}


inline void add(int &a, const int val) {
	a += val;
	if (a >= Mod) {
		a -= Mod;
	}
}

void init(int i, int dig) {
	memset(dp[i], 0, sizeof(dp[i]));
	for (int t = 0; t <= 9; t++) {
		dp[i][t == 3][t == 1][get(t, dig)]++;
	}
}



void merge(int i, int i1, int i2) {
	memset(dp[res - 1], 0, sizeof(dp[res - 1]));
	for (int t = 0; t < 3; t++) {
		for (int t1 = 0; t1 < 3; t1++) {
			int t2 = (t == 0 ? 0: (t == 1 ? t1: 2));
			for (int j = 0; j < 2; j++) {
				for (int k = 0; k < 2; k++) {
					for (int g = 0; g <= 1 - k; g++) {
						for (int f = 0; f < 2; f++) {
							add(dp[res - 1][j][f][t2], mul(dp[i1][j][k][t], dp[i2][g][f][t1]));
						}
					}
				}
			}
		}
	}
	for (int t = 0; t < 2; t++) {
		for (int t1 = 0; t1 < 2; t1++) {
			for (int k = 0; k < 3; k++) {
				dp[i][t][t1][k] = dp[res - 1][t][t1][k];
			}
		}
	}
}


void changed(int i, int val) {
	init(i, val);
	while (i >> 1 > 0) {
		i >>= 1;
		merge(i, i * 2, i * 2 + 1);
	}
}

int cnt;

void calc(int v, int vl, int vr, const int l, const int r) {
	if (vl > r || vr < l) {
		return;
	}
	if (l <= vl && vr <= r) {
		cnt++;
		if (cnt == 1) {
			for (int t = 0; t < 2; t++) {
				for (int t1 = 0; t1 < 2; t1++) {
					for (int k = 0; k < 3; k++) {
						dp[res][t][t1][k] = dp[v][t][t1][k];
					}
				}
			}
		} else {
			merge(res, res, v);
		}
		return;
	}
	calc(v * 2, vl, (vl + vr) / 2, l, r);
	calc(v * 2 + 1, (vl + vr) / 2 + 1, vr, l, r);
}


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
//	freopen("input.in", "r", stdin);
	cin >> n >> q;
	cin >> x;
	while (ss < n) {
		ss <<= 1;
	}
	for (int i = 0; i < n; i++) {
		init(ss + i, x[i] - '0');
	}
	for (int j = ss - 1; j >= 1; j--) {
		merge(j, j * 2, j * 2 + 1);
	}
	cnt = 0;
	calc(1, 1, ss, 1, n);
	int ans = 0;
	for (int k = 0; k < 2; k++) {
		for (int j = 0; j < 2; j++) {
			add(ans, dp[res][k][j][0]);
			add(ans, dp[res][k][j][1]);
		}
	}
	cout << ans << '\n';
	for (int it = 0; it < q; it++) {
		int t;
		cin >> t;
		if (t == 1) {
			int l, r;
			cin >> l >> r;
			cnt = 0;
			calc(1, 1, ss, l, r);
			int ans = 0;
			for (int k = 0; k < 2; k++) {
				for (int j = 0; j < 2; j++) {
					add(ans, dp[res][k][j][0]);
					add(ans, dp[res][k][j][1]);
				}
			}
			cout << ans << '\n';
		} else {
			int pi, di;
			cin >> pi >> di;
			changed(ss + pi - 1, di);
		}
	}
	return 0;
}

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