Submission #685070

#	Time	Username	Problem	Language	Result	Execution time	Memory
685070		vovamr	Lucky Numbers (RMI19_lucky)	C++17	100 / 100	182 ms	24664 KiB

lucky

#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 (stderr)

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 / 14
• Subtask 2: 14 / 14
• Subtask 3: 9 / 9
• Subtask 4: 27 / 27
• Subtask 5: 9 / 9
• Subtask 6: 27 / 27