oj.uz

Submission #198083

# Submission time Handle Problem Language Result Execution time Memory
198083 2020-01-24T16:02:29 Z model_code Lucky Numbers (RMI19_lucky) C++17
46 / 100
 200 ms 28152 KB 
/**
* user:  shekhovtsov-1b3
* fname: Alexandar
* lname: Shekhovtsov
* task:  lucky
* score: 46.0
* date:  2019-10-10 06:48:04.984554
*/
#include "bits/stdc++.h"

#define pb push_back
#define mp make_pair
#define mt make_tuple
#define x first
#define y second
#define len(v) ((int)v.size())

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;


template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
	for (const T &x : v) {
		os << x << " ";
	}
	return os;
}

template<class A, class B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
	os << p.x << " " << p.y;
	return os;
}

const ll MOD = 1e9 + 7;

void add(ll &x, ll y) {
	x += y;
	if (x >= MOD) x -= MOD;
}

ll mul(ll x, ll y) {
	return (x * y) % MOD;
}

struct Elem {
	int l = 0;
	ll mat[2][2];
	ll base[2][2];
	void clear() {
		for (int i = 0; i < 2; i++)
			for (int j = 0; j < 2; j++) 
				base[i][j] = mat[i][j] = 0;
	}
	Elem() {
		clear();
	}
	Elem(ll digit) {
		clear();
		l = 1;
			
		for (int i = 0; i < digit; i++) {
			mat[(i == 3)][(i == 1)]++;	
		}
		base[(digit == 3)][(digit == 1)]++;	
	}

	ll value() {
		ll r = 0;
		for (int i = 0; i < 2; i++) {
			for (int j = 0; j < 2; j++) {
				add(r, base[i][j]);
				add(r, mat[i][j]);
			}
		}
		return r;
	}
};

#define set huet

const int N = (1 << 17);

Elem merge(Elem, Elem);

Elem construct[N + 5];
// Elem construct(int l) {
// 	if (l == 0) return Elem(9);
// 	if (l == 1) return Elem(9);
// 	return merge(construct(l - 1), Elem(9));
// }

Elem merge(Elem a, Elem b) {
	Elem d = construct[b.l];
	Elem c;
	for (int i = 0; i < 2; i++) {
		for (int j = 0; j < 2; j++) {
			for (int k = 0; k < 2; k++) {
				if (j == 1 && k == 1) continue;
				for (int t = 0; t < 2; t++) {
					add(c.mat[i][t], mul(a.mat[i][j], (d.mat[k][t] + d.base[k][t])));
					add(c.mat[i][t], mul(a.base[i][j], b.mat[k][t]));
					add(c.base[i][t], mul(a.base[i][j], b.base[k][t]));
				}
			}
		}
	}
	c.l = a.l + b.l;
	return c;
}
string s;

ll queryst(int n) {
	int cnt = 0;
	for (int i = 0; i <= n; i++) {
		string t = to_string(i);	
		bool fail = false;
		for (int j = 0; j < len(t) - 1; j++) {
			if (t[j] == '1' && t[j + 1] == '3') fail = true;
		}
		cnt += !fail;
	}
	return cnt;
}

ll querys(int n) {
	string t = to_string(n);
	Elem e(t[0] - '0');
	for (int i = 1; i < len(t); i++)
		e = merge(e, Elem(t[i] - '0'));
	return e.value();
}


Elem T[2 * N + 1];

void set(int i, Elem e) {
	i += N - 1;
	T[i] = e;
	while (i) {
		i = (i - 1) / 2;
		T[i] = merge(T[i * 2 + 1], T[i * 2 + 2]);
	}
}

ll query(int l, int r) {
	l += N - 1;
	r += N - 2;
	if (l == r) return T[l].value();

	Elem A = T[l];
	Elem B = T[r];

	for (; (l - 1) / 2 != (r - 1) / 2; l = (l - 1) / 2, r = (r - 1) / 2) {
		if (l & 1) A = merge(A, T[l + 1]);
		if (~r & 1) B = merge(T[r - 1], B);
	}

	return merge(A, B).value();
}

signed main(int argc, char const *argv[]) {
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	construct[0] = construct[1] = Elem(9);
	for (int i = 2; i < N + 5; i++) {
		construct[i] = merge(construct[i - 1], Elem(9));
	}
	// for (int i = 0; i < 1444; i++) {
	// 	if (querys(i) != queryst(i)) {
	// 		cout << i << ": " << querys(i) << " " << queryst(i) << endl;
	// 	}
	// }
	// Elem a(1);
	// Elem b(0);
	// cout << merge(a, b).value();	
	// return 0;
	int n, q;
	cin >> n >> q;
	cin >> s;
	for (int i = 0; i < len(s); i++)
		set(i, Elem(s[i] - '0'));
	cout << query(0, len(s)) << "\n";
	for (int i = 0; i < q; i++) {
		int type;
		cin >> type;
		if (type == 2) {
			int j;
			string value;
			cin >> j >> value;
			j--;
			set(j, Elem(value[0] - '0'));
			// s[j] = value[0];
		} else {
			int l, r;
			cin >> l >> r;
			l--;
			cout << query(l, r) << "\n";
		}
	}
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28024 KB Output is correct
2 Correct 46 ms 27952 KB Output is correct
3 Correct 57 ms 28080 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28024 KB Output is correct
2 Correct 46 ms 27952 KB Output is correct
3 Correct 57 ms 28080 KB Output is correct
4 Correct 52 ms 27964 KB Output is correct
5 Correct 52 ms 28076 KB Output is correct
6 Correct 49 ms 27992 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 28116 KB Output is correct
2 Correct 108 ms 28124 KB Output is correct

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 28116 KB Output is correct
2 Correct 108 ms 28124 KB Output is correct
3 Execution timed out 311 ms 28152 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28024 KB Output is correct
2 Correct 46 ms 27952 KB Output is correct
3 Correct 57 ms 28080 KB Output is correct
4 Correct 52 ms 27964 KB Output is correct
5 Correct 52 ms 28076 KB Output is correct
6 Correct 49 ms 27992 KB Output is correct
7 Correct 97 ms 28116 KB Output is correct
8 Correct 108 ms 28124 KB Output is correct
9 Correct 93 ms 28072 KB Output is correct
10 Correct 113 ms 28128 KB Output is correct

Subtask #6
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 28024 KB Output is correct
2 Correct 46 ms 27952 KB Output is correct
3 Correct 57 ms 28080 KB Output is correct
4 Correct 52 ms 27964 KB Output is correct
5 Correct 52 ms 28076 KB Output is correct
6 Correct 49 ms 27992 KB Output is correct
7 Correct 97 ms 28116 KB Output is correct
8 Correct 108 ms 28124 KB Output is correct
9 Execution timed out 311 ms 28152 KB Time limit exceeded
10 Halted 0 ms 0 KB -