oj.uz

Submission #258118

# Submission time Handle Problem Language Result Execution time Memory
258118 2020-08-05T11:47:01 Z oolimry Lucky Numbers (RMI19_lucky) C++14
28 / 100
 3 ms 3456 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;
	
	return val;
}

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);
	val.cnt -= l.cnttail * ways(r.len-1);
	fix(val.cnt);
	
	val.cnttail = l.cnt * ways(r.len-1);
	if(r.len >= 2) val.cnttail -= l.cnttail * ways(r.len-2);
	fix(val.cnttail);
	
	val.cnthead = l.cnthead * ways(r.len);
	val.cnthead -= l.cntboth * ways(r.len-1);
	fix(val.cnthead);
	
	val.cntboth = l.cnthead * ways(r.len-1);
	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.cnthead;
			if(l.isTail) val.cnthead -= r.cnthead;
			fix(val.cnthead);
			
			val.cntboth += r.cntboth;
			if(l.isTail) val.cntboth -= r.cntboth;
			fix(val.cnttail);
		}
		
		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;
	
	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 s, int x){
		if(s == e){
			val = basic(x);
			return;
		}
		if(s <= m) l->update(s,x);
		else r->update(s,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 <= 100000;i++){
		ONE[i]  = ALL[i-1];
		ALL[i] = ALL[i-1] * 10 - ONE[i-1];
		fix(ALL[i]);
		//if(i <= 6) cout << i << " " << ALL[i] << "\n";
	}
	
	root = new node(0,n-1);
	
	
	data D = root->val;
	int ans = D.cnt;
	if(D.isOk) ans++;
	fix(ans);
	cout << ans;
	
	//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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 3456 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
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 Incorrect 3 ms 3456 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
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 Incorrect 3 ms 3456 KB Output isn't correct
8 Halted 0 ms 0 KB -