oj.uz

Submission #198082

# Submission time Handle Problem Language Result Execution time Memory
198082 2020-01-24T16:02:00 Z model_code Lucky Numbers (RMI19_lucky) C++17
100 / 100
 133 ms 11548 KB 
/**
* 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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 376 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 368 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1220 KB Output is correct
2 Correct 56 ms 1656 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 1220 KB Output is correct
2 Correct 56 ms 1656 KB Output is correct
3 Correct 111 ms 10616 KB Output is correct
4 Correct 113 ms 10668 KB Output is correct
5 Correct 122 ms 11144 KB Output is correct
6 Correct 129 ms 11548 KB Output is correct
7 Correct 129 ms 11476 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 368 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 43 ms 1220 KB Output is correct
8 Correct 56 ms 1656 KB Output is correct
9 Correct 46 ms 1188 KB Output is correct
10 Correct 63 ms 1708 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 2 ms 400 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 368 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 43 ms 1220 KB Output is correct
8 Correct 56 ms 1656 KB Output is correct
9 Correct 111 ms 10616 KB Output is correct
10 Correct 113 ms 10668 KB Output is correct
11 Correct 122 ms 11144 KB Output is correct
12 Correct 129 ms 11548 KB Output is correct
13 Correct 129 ms 11476 KB Output is correct
14 Correct 46 ms 1188 KB Output is correct
15 Correct 63 ms 1708 KB Output is correct
16 Correct 118 ms 10488 KB Output is correct
17 Correct 118 ms 10616 KB Output is correct
18 Correct 125 ms 10996 KB Output is correct
19 Correct 132 ms 11384 KB Output is correct
20 Correct 133 ms 11452 KB Output is correct