oj.uz

Submission #258159

# Submission time Handle Problem Language Result Execution time Memory
258159 2020-08-05T12:56:43 Z oolimry Lucky Numbers (RMI19_lucky) C++14
100 / 100
 57 ms 21752 KB 
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#define int long long
using namespace std;
typedef pair<int,int> ii;

///1 is tail (one)
///3 is head (three)
int mod = 1000000007;

void fix(int &x){
	x %= mod;
	if(x < 0) x += mod;
}

int arr[100005];
int ten[100005];

struct data{
	int cnt = 0;
	int cnttail = 0;
	int cnthead = 0;
	int cntboth = 0;
	int len = 1;
	
	bool isHead = false;
	bool isTail = false;
	bool isOk = true;
};

void out(data D){
	cout << "ways : " << D.cnt << "\n";
	cout << "waysHead : " << D.cnthead << "\n";
	cout << "waysTail : " << D.cnttail << "\n";
	cout << "waysBoth : " << D.cntboth << "\n";
	cout << "len : " << D.len << "\n\n";
}

data basic(int x){
	data val;
	val.cnt = x;
	
	if(x > 1){
		val.cnttail = 1;
	}
	if(x > 3){
		val.cnthead = 1;
	}
	if(x == 1) val.isTail = true;
	if(x == 3) val.isHead = true;
	val.isOk = true;
	
	return val;
}
int B[11];

int ALL[100005];
int ONE[100005];
inline int ways(int digits){
	if(digits == 0) return 1;
	return ALL[digits-1];
}

data merge(data l, data r){
	data val;
	
	///consider when l is not bounded
	val.cnt = l.cnt * ways(r.len);
	fix(val.cnt);
	val.cnt -= l.cnttail * ways(r.len-1);
	fix(val.cnt);
	
	val.cnttail = l.cnt * ways(r.len-1);
	fix(val.cnttail);
	if(r.len >= 2) val.cnttail -= l.cnttail * ways(r.len-2);
	fix(val.cnttail);
	
	val.cnthead = l.cnthead * ways(r.len);
	fix(val.cnthead);
	val.cnthead -= l.cntboth * ways(r.len-1);
	fix(val.cnthead);
	
	val.cntboth = l.cnthead * ways(r.len-1);
	fix(val.cntboth);
	if(r.len >= 2) val.cntboth -= l.cntboth * ways(r.len-2); 
	fix(val.cntboth);
	
	///when l is bounded
	if(l.isOk){
		if(l.isHead){
			val.cnthead += r.cnt;
			if(l.isTail) val.cnthead -= r.cnthead;
			fix(val.cnthead);
			
			val.cntboth += r.cnttail;
			if(l.isTail) val.cntboth -= r.cntboth;
			fix(val.cntboth);
		}
		
		val.cnt += r.cnt;
		if(l.isTail) val.cnt -= r.cnthead;
		fix(val.cnt);
		
		val.cnttail += r.cnttail;
		if(l.isTail) val.cnttail -= r.cntboth;
		fix(val.cnttail);
	}	
	
	val.len = l.len + r.len;
	val.isHead = l.isHead;
	val.isTail = r.isTail;
	val.isOk = (l.isOk && r.isOk);
	if(l.isTail && r.isHead) val.isOk = false;
	
	val.cnt %= mod;
	val.cnttail %= mod;
	val.cnthead %= mod;
	val.cntboth %= mod;
	
	return val;
}

struct node{
	
	int s, e, m;
	data val;
	node *l, *r;
	
	node(int S, int E){
		s = S, e = E; m =(s+e)/2;
		if(s == e){
			val = basic(arr[s]);
			//cout << s << " " << e << ":\n";
			//out(val);
		}
		else{
			l = new node(s,m);
			r = new node(m+1,e);
			val = merge(l->val, r->val);
			//cout << s << " " << e << ":\n";
			//out(val);
		}
	}
	
	void update(int P, int x){
		if(s == e){
			val = basic(x);
			//out(val);
			return;
		}
		if(P <= m) l->update(P,x);
		else r->update(P,x);
		
		val = merge(l->val, r->val);
	}
	
	
	data query(int S, int E){
		if(s == S && e == E) return val;
		else if(E <= m) return l->query(S,E);
		else if(S >= m+1) return r->query(S,E);
		else return merge(l->query(S,m), r->query(m+1,E));
	}
	
} *root;



signed main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n, Q; cin >> n >> Q;
	
	string s; cin >> s;
	for(int i = 0;i < n;i++){
		arr[i] = (s[i] - '0');
	}
	
	ALL[0] = 10;
	ONE[0] = 1;
	for(int i = 1;i <= 100003;i++){
		ONE[i]  = ALL[i-1];
		ALL[i] = ALL[i-1] * 10 - ONE[i-1];
		ALL[i] %= mod;
		fix(ALL[i]);
	}
	
	root = new node(0,n-1);
	
	data D = root->val;
	int ans = D.cnt;
	if(D.isOk) ans++;
	fix(ans);
	cout << ans << '\n';
		
	while(Q--){
		int type = 0;
		cin >> type;
		
		if(type == 1){
			int l, r; cin >> l >> r;
			l--, r--;
			
			
			data D = root->query(l,r);
			int ans = D.cnt;
			if(D.isOk) ans++;
			fix(ans);
			cout << ans << "\n";
			
			/*
			data D = basic(arr[l]);
			for(int i = l+1;i <= r;i++){
				D = merge(D, basic(arr[i]));
			}
			int ans = D.cnt;
			if(D.isOk) ans++;
			fix(ans);
			cout << ans << "\n";
			*/
		}
		else{
			int i, x; cin >> i >> x;
			arr[i-1] = x;
			root->update(i-1,x);
		}
	}
	
	
	//cout << "\n" << ways(2);
}

/*
 * 
def chk(x):
	ans = 0;
	for i in range(x):
		s = str(i)
		for j in range(len(s)-1):
			if s[j] == '1' and s[j+1] == '3':
				ans+=1
				break
	return x - ans
*/

Subtask #1
14.0 / 14.0

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

Subtask #2
14.0 / 14.0

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

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3584 KB Output is correct
2 Correct 22 ms 3968 KB Output is correct

Subtask #4
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 3584 KB Output is correct
2 Correct 22 ms 3968 KB Output is correct
3 Correct 49 ms 17784 KB Output is correct
4 Correct 54 ms 17784 KB Output is correct
5 Correct 54 ms 19704 KB Output is correct
6 Correct 54 ms 21624 KB Output is correct
7 Correct 57 ms 21752 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 2 ms 1920 KB Output is correct
7 Correct 18 ms 3584 KB Output is correct
8 Correct 22 ms 3968 KB Output is correct
9 Correct 18 ms 3584 KB Output is correct
10 Correct 23 ms 3968 KB Output is correct

Subtask #6
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1920 KB Output is correct
2 Correct 2 ms 1920 KB Output is correct
3 Correct 2 ms 1920 KB Output is correct
4 Correct 2 ms 1920 KB Output is correct
5 Correct 2 ms 1920 KB Output is correct
6 Correct 2 ms 1920 KB Output is correct
7 Correct 18 ms 3584 KB Output is correct
8 Correct 22 ms 3968 KB Output is correct
9 Correct 49 ms 17784 KB Output is correct
10 Correct 54 ms 17784 KB Output is correct
11 Correct 54 ms 19704 KB Output is correct
12 Correct 54 ms 21624 KB Output is correct
13 Correct 57 ms 21752 KB Output is correct
14 Correct 18 ms 3584 KB Output is correct
15 Correct 23 ms 3968 KB Output is correct
16 Correct 42 ms 17664 KB Output is correct
17 Correct 44 ms 17684 KB Output is correct
18 Correct 46 ms 19704 KB Output is correct
19 Correct 52 ms 21624 KB Output is correct
20 Correct 52 ms 21632 KB Output is correct