oj.uz

Submission #396547

# Submission time Handle Problem Language Result Execution time Memory
396547 2021-04-30T09:20:36 Z jakubd Trol (COCI19_trol) C++17
10 / 50
 2 ms 312 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

template<typename T> void ckmin(T &a, T b) { if (a > b) a = b; }
template<typename T> void ckmax(T &a, T b) { if (a < b) a = b; }

#define pb push_back
#define mp make_pair
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define manytests int TT;cin >> TT; while (TT--)

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define FORd(i,a,b) for (int i = (a); i >= (b); --i)

int dx[8] = {-1, 1, 0, 0, 1, 1, -1, -1}, dy[8] = {0, 0, 1, -1, 1, 1, -1, -1};
int INF = 1e9;

#define ll long long
#define ld long double
#define fi first
#define se second
#define rev reverse

#define vi vector<int>
#define vl vector<ll>
#define vc vector<char>
#define vd vector<double>
#define vs vector<string>
#define vld vector<ld>
#define vb vector<bool>
#define vvi vector<vi>
#define pii pair<int, int>
#define pl pair<ll, ll>
#define pld pair<ld, ld>
#define vpi vector<pii>
#define vpl vector<pl>
#define vpld vector<pld>

ll solve(ll x) {
    if (x < 10) return x * (x + 1) / 2;
    ll d = (int)log10(x);
    vl a(d+1);
    a[1]=45;
    FOR(i,2,d+1) a[i] = a[i-1]*10+45*((int)ceil(pow(10,i-1)));
    ll p = (int)ceil(pow(10,d));
    ll msd = x/p;
    return (int)(msd * a[d] + (msd * (msd - 1) / 2) * p + msd * (1 + x % p) + solve(x % p));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    manytests {
        ll l, r;
        cin >> l >> r;
        cout << solve(r) - solve(l - 1) << "\n";
    }

    return 0;
}

Subtask #1
10.0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Incorrect 2 ms 312 KB Output isn't correct
4 Incorrect 1 ms 204 KB Output isn't correct
5 Incorrect 2 ms 204 KB Output isn't correct