oj.uz

Submission #685069

# Submission time Handle Problem Language Result Execution time Memory
685069 2023-01-23T08:53:32 Z vovamr Lucky Numbers (RMI19_lucky) C++17
64 / 100
 162 ms 24700 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) ++F[1][d == 1 ? 1 : (d == 3 ? 2 : 0)][d == 1 ? 1 : (d == 3 ? 2 : 0)];
	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 - 1);
		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:130:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  130 |  int m = vl + vr >> 1;
      |          ~~~^~~~
lucky.cpp: In function 'void dbg(int, int, int)':
lucky.cpp:152:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  152 |  int m = vl + vr >> 1;
      |          ~~~^~~~
lucky.cpp: In function 'void upd(int, int, int, int, int)':
lucky.cpp:159:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  159 |  int m = vl + vr >> 1;
      |          ~~~^~~~
lucky.cpp: In function 'node get(int, int, int, int, int)':
lucky.cpp:166:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  166 |  int m = vl + vr >> 1;
      |          ~~~^~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24132 KB Output is correct
2 Correct 23 ms 24120 KB Output is correct
3 Correct 25 ms 24128 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24132 KB Output is correct
2 Correct 23 ms 24120 KB Output is correct
3 Correct 25 ms 24128 KB Output is correct
4 Correct 23 ms 24152 KB Output is correct
5 Correct 22 ms 24224 KB Output is correct
6 Correct 22 ms 24204 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 24284 KB Output is correct
2 Correct 98 ms 24304 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 24284 KB Output is correct
2 Correct 98 ms 24304 KB Output is correct
3 Correct 132 ms 24588 KB Output is correct
4 Correct 132 ms 24524 KB Output is correct
5 Correct 150 ms 24620 KB Output is correct
6 Correct 162 ms 24652 KB Output is correct
7 Correct 162 ms 24700 KB Output is correct

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24132 KB Output is correct
2 Correct 23 ms 24120 KB Output is correct
3 Correct 25 ms 24128 KB Output is correct
4 Correct 23 ms 24152 KB Output is correct
5 Correct 22 ms 24224 KB Output is correct
6 Correct 22 ms 24204 KB Output is correct
7 Correct 80 ms 24284 KB Output is correct
8 Correct 98 ms 24304 KB Output is correct
9 Incorrect 80 ms 24200 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 24132 KB Output is correct
2 Correct 23 ms 24120 KB Output is correct
3 Correct 25 ms 24128 KB Output is correct
4 Correct 23 ms 24152 KB Output is correct
5 Correct 22 ms 24224 KB Output is correct
6 Correct 22 ms 24204 KB Output is correct
7 Correct 80 ms 24284 KB Output is correct
8 Correct 98 ms 24304 KB Output is correct
9 Correct 132 ms 24588 KB Output is correct
10 Correct 132 ms 24524 KB Output is correct
11 Correct 150 ms 24620 KB Output is correct
12 Correct 162 ms 24652 KB Output is correct
13 Correct 162 ms 24700 KB Output is correct
14 Incorrect 80 ms 24200 KB Output isn't correct
15 Halted 0 ms 0 KB -