Submission #710974

#	Time	Username	Problem	Language	Result	Execution time	Memory
710974		dozer	Trol (COCI19_trol)	C++14	50 / 50	1 ms	324 KiB

trol

#include <bits/stdc++.h>
using namespace std;
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 200005
#define int long long


const int modulo = 1e9 + 7;


int32_t main()
{
	fastio();

	auto f = [&](int tmp){
		while(tmp > 9)
		{
			int res = 0;
			while(tmp > 0)
			{
				res += tmp % 10;
				tmp /= 10;
			}
			tmp = res;
		}
		return tmp;
	};

	int q;
	cin>>q;
	while(q--)
	{
		int l, r;
		cin>>l>>r;
		if (r - l < 20)
		{
			int ans = 0;
			for (int i = l; i <= r; i++)
				ans += f(i);
			cout<<ans<<endl;
			continue;
		}
		int ll = f(l), rr = f(r);
		//cout<<ll<<sp<<rr<<endl;
		int ans = 0;
		if (ll != 1)
		{
			ans += 45 - ll * (ll - 1) / 2;
			l += 9 - ll + 1;
		}
		if (rr != 9)
		{
			ans += rr * (rr + 1) / 2;
			r -= rr; 
		}

		ans += (r - l + 1) * 5;
		//cout<<l<<sp<<r<<endl;
		cout<<ans<<endl;
	}

	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
}

• Subtask 1: 50 / 50