Submission #1347938

#TimeUsernameProblemLanguageResultExecution timeMemory
1347938vladmart09Trol (COCI19_trol)C++20
50 / 50
0 ms344 KiB

#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#include <random>
#include <queue>
#include <numeric>
#include <array>
#include <iomanip>
#include <stack>
#include <chrono>
#include <climits>

using namespace std;

using ll = long long;
using ld = long double;
using vi = vector<ll>;
using vii = vector<vi>;
using viii = vector<vii>;
using pi = pair<ll, ll>;
using vpi = vector<pi>;
using vb = vector<bool>;
using vs = vector<string>;

#define vec vector
#define cmax(x, y) x = max({x, y})
#define cmin(x, y) x = min({x, y})
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()

const ll N = 3e5 + 5, MOD = 1e9 + 7, INF = (ll)1e18, K = 20;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void solve() {
	ll q; cin >> q;

	auto get = [&](ll r) -> ll {
		return r / 9 * 9 * 10 / 2 + (r % 9) * (r % 9 + 1) / 2;
	};

	while (q--) {
		ll l, r; cin >> l >> r;

		ll ans = get(r) - get(l - 1);

		cout << ans << '\n';
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	long long tt = 1;
	//cin >> tt;

	while (tt--) {
		solve();
		cout << '\n';
	}

	return 0;
}

/*


Задачу нужно отдельно решать для разных длин путей

2: колво путей
3: с помощью обычного cnt проще всего
4: фиксировать ребро, там все просто
5: фиксировать вершину, сложность в том чтобы не было тле



[0, 9], [1, ]



























Какие темы повторить:
1) мст
2) 2сат
3) точки артикуляции
4) ксор базис
5) эйлеровый цикл, путь
6) кмп
7) конвекс хулл
8) вафельное дерево
9) суфиксный массив
10) суффиксный автомат
11) ним

*/
#Verdict Execution timeMemoryGrader output
Fetching results...