Submission #1206921

---

Source Code Expand

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#define rep(a) for(int i=0;i<a;i++)
#define nrep(a,b) for(int i=a;i<b;i++)
#define mrep(a) for(int i=a;i>=0;i--)
#define ll long long
#define INF 1145141919
using namespace std;

vector<ll> dp;

ll check(ll n){
	string str = to_string(n);
	rep(str.length()) if (str[i] == '4' || str[i] == '9') return true;
	return false;
}

ll solv(ll n){
	ll ans = 0;
	rep(n) if (check(i + 1)) ans++;
	return ans;
}

ll pow(ll a, ll b){
	ll ret = 1;
	rep(b) ret *= a;
	return ret;
}

ll fun(ll index, string str){
	ll ans = 0, count = index-1;
	nrep(str.length()-index,str.length()) ans = ans + (pow(10, count--)*(str[i] - '0'));
	return ans;
}

ll solv_fast(ll n){
	string str = to_string(n);
	ll length = str.length();
	dp.resize(length);
	dp[0] = 0;
	nrep(1,length) dp[i] = dp[i - 1] * 8 + pow(10, i-1) * 2;
	ll ans = 0;
	rep(length){
		if (str[i] - '0' < 4){
			ans += ((str[i] - '0')*dp[length - i - 1]);
		}
		else if (str[i] - '0' == 4){
			//ans += (3 * dp[length - i - 1]) + fun(length - i - 1, str);
			ans += (4 * dp[length - i - 1]) + fun(length - i - 1, str) + 1;
			break;
		}
		else if (str[i] - '0' < 9){
			ans += (str[i] - '0')*dp[length - i - 1]+pow(10,length-1-i)-dp[length-i-1];
		}
		else{
			//ans += (3 * dp[length - i - 1]) + fun(length - i - 1, str);
			ans += (9 * dp[length - i - 1])+pow(10,length-1-i)-dp[length-i-1] + fun(length - i - 1, str) + 1;
			break;
		}
	}
	return ans;
}

//最長部分増加列
ll long_retu(ll n, const vector<ll> &root_array){
	fill(dp.begin(), dp.end(), INF);
	rep(n) *lower_bound(dp.begin(), dp.end(), root_array[i]) = root_array[i];
	return lower_bound(dp.begin(),dp.end(), INF) - dp.begin();
}

int main(){
	ll a, b; cin >> a>> b;
	ll ans = solv_fast(b) - solv_fast(a);
	if (check(a)) ans++;
	cout << ans << endl;
	/*
	ll n = 1979;
	cout << solv(n) << endl;
	cout << solv_fast(n) << endl;
	*/

	return 0;
}

Submission Info

Judge Result