제출 #1157242

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1157242		tayogaming123	Trol (COCI19_trol)	C++20	20 / 50	8 ms	12104 KiB

trol

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MAX_PRECOMPUTE = 1000000;  // Precompute up to 10^6

vector<int> digitRoot(MAX_PRECOMPUTE + 1);
vector<ll> prefixSum(MAX_PRECOMPUTE + 1);

// Function to compute digit root
int computeDigitRoot(ll num) {
    if (num == 0) return 0;
    return 1 + (num - 1) % 9;
}

// Precompute digit roots and prefix sums up to 10^6
void precompute() {
    for (ll i = 1; i <= MAX_PRECOMPUTE; i++) {
        digitRoot[i] = computeDigitRoot(i);
        prefixSum[i] = prefixSum[i - 1] + digitRoot[i];
    }
}

// Function to calculate sum in range L to R
ll querySum(ll L, ll R) {
    if (R <= MAX_PRECOMPUTE) {
        return prefixSum[R] - prefixSum[L - 1];  // Direct lookup
    }
    ll sum = 0;
    for (ll i = L; i <= R; i++) {
        sum += computeDigitRoot(i);
        if (i > MAX_PRECOMPUTE) break;  // Stop unnecessary looping
    }
    return sum;
}

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

    precompute();  // Precompute values for fast lookup

    int Q;
    cin >> Q;
    while (Q--) {
        ll L, R;
        cin >> L >> R;
        cout << querySum(L, R) << '\n';
    }

    return 0;
}

• Subtask 1: 20 / 50