Submission #258159

#	Time	Username	Problem	Language	Result	Execution time	Memory
258159		oolimry	Lucky Numbers (RMI19_lucky)	C++14	100 / 100	57 ms	21752 KiB

lucky

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