oj.uz

Submission #685070

# Submission time Handle Problem Language Result Execution time Memory
685070 2023-01-23T09:06:51 Z vovamr Lucky Numbers (RMI19_lucky) C++17
100 / 100
 182 ms 24664 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define fi first
#define se second
#define ll long long
#define ld long double
#define sz(x) ((int)(x).size())
#define all(x) 	(x).begin(), (x).end()
#define pb push_back
#define mpp make_pair
#define ve vector
using namespace std;
using namespace __gnu_pbds;
template<class T> using oset = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
const ll inf = 1e18; const int iinf = 1e9;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <typename T> inline bool chmin(T& a, T b) { return (a > b ? a = b, 1 : 0); }
template <typename T> inline bool chmax(T& a, T b) { return (a < b ? a = b, 1 : 0); }

constexpr int md = 1e9 + 7; constexpr int iv2 = (md + 1) / 2;
inline int add(int a, const int &b) { if((a+=b)>=md)a-=md; return a; }
inline void adds(int &a, const int &b) { if((a+=b)>=md)a-=md; }
inline int sub(int a, const int &b) { if((a-=b)<0)a+=md; return a; }
inline void subs(int &a, const int &b) { if ((a-=b)<0)a+=md; }
inline int mul(int a, const int &b) { return 1ll*a*b%md; }
inline void muls(int &a, const int &b) { a=(1ll*a*b%md); }
inline int bp(int a, int n) { int res = 1;
	for (; n; n >>= 1, muls(a, a)) {
		if (n & 1) muls(res, a);
	} return res;
}
inline int inv(int a) { return bp(a, md - 2); }

const int N = 1e5 + 100;

int F[N][3][3], ok[N];

inline void calc() {
	for (int d = 0; d < 10; ++d) {
		int z = (d == 1 ? 1 : (d == 3 ? 2 : 0));
		++F[1][z][z];
	}
	for (int len = 2; len < N; ++len) {
		for (int fprev : {0, 1, 2}) for (int ffir : {0, 1, 2}) {
			for (pii cur : {mpp(0, 8), mpp(1, 1), mpp(2, 1)}) {
				if (!(cur.fi == 1 && fprev == 2)) {
					adds(F[len][cur.fi][ffir], mul(cur.se, F[len - 1][fprev][ffir]));
				}
			}
		}
	}
	/*
	for (int len = 1; len < 6; ++len) {
		for (int a : {0, 1, 2}) for (int b : {0, 1, 2}) {
			if (len < 3 && F[len][a][b]) {
				cerr << "number of length " << len << " with ";
				cerr << "first dig = " << (a == 0 ? "not 1,3" : (a == 1 ? "1" : "3")) << " and ";
				cerr << "last dig = " << (b == 0 ? "not 1,3" : (b == 1 ? "1" : "3")) << " = " << F[len][a][b] << '\n';
			}
		}
	}
	*/
}

struct node {
	int ans;
	short fir, last;
	bool good;

	int len;

	int cnt[3][3]; // beg is {else, 1, 3}, end is {else, 1, 3}

	node(int x) {
		len = 1;
		ans = max(0, x);
		memset(cnt, 0, sizeof(cnt));
		for (int d = 0; d < x; ++d) {
			int z = (d == 1 ? 1 : (d == 3 ? 2 : 0));
			++cnt[z][z];
		}
		fir = last = x;
		good = 1;
	}
	node() : ans(0) {
		memset(cnt, 0, sizeof(cnt));
	}
};

inline node mg(const node &a, const node &b) {
	node res;
	res.fir = a.fir;
	res.last = b.last;
	res.len = a.len + b.len;
	res.good = a.good & b.good & (!(a.last == 1 && b.fir == 3));

	for (int fa : {0, 1, 2}) for (int la : {0, 1, 2}) {
		for (int aa : {0, 1, 2}) for (int bb : {0, 1, 2}) {
			if (!(la == 1 && aa == 2)) {
				int w = mul(a.cnt[fa][la], F[b.len][aa][bb]);
//				cout << fa << " " << la << " " << aa << " " << bb << ": " << w << '\n';
				adds(res.ans, w);
				adds(res.cnt[fa][bb], w);
			}
		}
/*
		if (b.good && !(la == 1 && b.fir == 3)) {
			adds(res.ans, a.cnt[fa][la]);
			adds(res.cnt[fa][b.last == 1 ? 1 : (b.last == 3 ? 2 : 0)], a.cnt[fa][la]);
		}
*/
	}

	if (a.good) {
		for (int fb : {0, 1, 2}) for (int lb : {0, 1, 2}) {
			if (a.last == 1 && fb == 2) continue;
			const int &w = b.cnt[fb][lb];
			adds(res.ans, w);
			adds(res.cnt[a.fir == 1 ? 1 : (a.fir == 3 ? 2 : 0)][lb], w);
		}
	}

	return res;
}

int a[N];
node t[4 * N];
inline void build(int v, int vl, int vr) {
	if (vl == vr) return void(t[v] = node(a[vl]));
	int m = vl + vr >> 1;
	build(2 * v + 1, vl, m);
	build(2 * v + 2, m + 1, vr);
	t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
}

inline void debug_node(int v, int vl, int vr) {
	cout << v << " [" << vl + 1 << ", " << vr + 1 << "]:" << '\n';
	cout << "ans = " << t[v].ans << '\n';
	cout << "fir, last, good = " << t[v].fir << " " << t[v].last << " " << t[v].good << '\n';
	for (int a : {0, 1, 2}) {
		for (int b : {0, 1, 2}) {
			cout << "start is ";
			cout << (a == 0 ? "not 1,3" : (a == 1 ? "1" : "3")) << ", end is ";
			cout << (b == 0 ? "not 1,3" : (b == 1 ? "1" : "3")) << " -> " << t[v].cnt[a][b] << '\n';
		}
	}
	cout << '\n';
}
inline void dbg(int v, int vl, int vr) {
	debug_node(v, vl, vr);
	if (vl == vr) return;
	int m = vl + vr >> 1;
	dbg(2 * v + 1, vl, m);
	dbg(2 * v + 2, m + 1, vr);
}

inline void upd(int v, int vl, int vr, int pos, int x) {
	if (vl == vr) return void(t[v] = node(x));
	int m = vl + vr >> 1;
	if (pos <= m) upd(2 * v + 1, vl, m, pos, x);
	else upd(2 * v + 2, m + 1, vr, pos, x);
	t[v] = mg(t[2 * v + 1], t[2 * v + 2]);
}
inline node get(int v, int vl, int vr, int l, int r) {
	if (vl == l && vr == r) return t[v];
	int m = vl + vr >> 1;
	if (r <= m) return get(2 * v + 1, vl, m, l, r);
	else if (l > m) return get(2 * v + 2, m + 1, vr, l, r);
	else return mg(get(2*v+1,vl,m,l,m),get(2*v+2,m+1,vr,m+1,r));
}

inline void solve() { calc();

	int n, q;
	cin >> n >> q;
	for (int i = 0; i < n; ++i) {
		char x;
		cin >> x;
		a[i] = x - '0';
	}
	build(0, 0, n - 1);

//	dbg(0, 0, n - 1);
//	return;

	cout << add(t[0].ans, t[0].good) << '\n';

	while (q--) {
		int type;
		cin >> type;
		if (type == 2) {
			int pos, x;
			cin >> pos >> x;
			upd(0, 0, n - 1, --pos, x);
		}
		else {
			int l, r;
			cin >> l >> r;
			node ans = get(0, 0, n - 1, --l, --r);
			cout << add(ans.ans, ans.good) << '\n';
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int q = 1; // cin >> q;
	while (q--) solve();
	cerr << fixed << setprecision(3) << "Time execution: " << (double)clock() / CLOCKS_PER_SEC << endl;
}

Compilation message

lucky.cpp: In function 'void build(int, int, int)':
lucky.cpp:133:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  133 |  int m = vl + vr >> 1;
      |          ~~~^~~~
lucky.cpp: In function 'void dbg(int, int, int)':
lucky.cpp:155:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  155 |  int m = vl + vr >> 1;
      |          ~~~^~~~
lucky.cpp: In function 'void upd(int, int, int, int, int)':
lucky.cpp:162:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  162 |  int m = vl + vr >> 1;
      |          ~~~^~~~
lucky.cpp: In function 'node get(int, int, int, int, int)':
lucky.cpp:169:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |  int m = vl + vr >> 1;
      |          ~~~^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24140 KB Output is correct
2 Correct 22 ms 24112 KB Output is correct
3 Correct 23 ms 24116 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24140 KB Output is correct
2 Correct 22 ms 24112 KB Output is correct
3 Correct 23 ms 24116 KB Output is correct
4 Correct 22 ms 24176 KB Output is correct
5 Correct 22 ms 24168 KB Output is correct
6 Correct 22 ms 24196 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 24372 KB Output is correct
2 Correct 103 ms 24300 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 81 ms 24372 KB Output is correct
2 Correct 103 ms 24300 KB Output is correct
3 Correct 135 ms 24580 KB Output is correct
4 Correct 145 ms 24648 KB Output is correct
5 Correct 159 ms 24580 KB Output is correct
6 Correct 172 ms 24664 KB Output is correct
7 Correct 182 ms 24588 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24140 KB Output is correct
2 Correct 22 ms 24112 KB Output is correct
3 Correct 23 ms 24116 KB Output is correct
4 Correct 22 ms 24176 KB Output is correct
5 Correct 22 ms 24168 KB Output is correct
6 Correct 22 ms 24196 KB Output is correct
7 Correct 81 ms 24372 KB Output is correct
8 Correct 103 ms 24300 KB Output is correct
9 Correct 82 ms 24268 KB Output is correct
10 Correct 112 ms 24300 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 24140 KB Output is correct
2 Correct 22 ms 24112 KB Output is correct
3 Correct 23 ms 24116 KB Output is correct
4 Correct 22 ms 24176 KB Output is correct
5 Correct 22 ms 24168 KB Output is correct
6 Correct 22 ms 24196 KB Output is correct
7 Correct 81 ms 24372 KB Output is correct
8 Correct 103 ms 24300 KB Output is correct
9 Correct 135 ms 24580 KB Output is correct
10 Correct 145 ms 24648 KB Output is correct
11 Correct 159 ms 24580 KB Output is correct
12 Correct 172 ms 24664 KB Output is correct
13 Correct 182 ms 24588 KB Output is correct
14 Correct 82 ms 24268 KB Output is correct
15 Correct 112 ms 24300 KB Output is correct
16 Correct 141 ms 24644 KB Output is correct
17 Correct 133 ms 24456 KB Output is correct
18 Correct 150 ms 24656 KB Output is correct
19 Correct 164 ms 24640 KB Output is correct
20 Correct 173 ms 24596 KB Output is correct