1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

using i128 = __int128_t;
void solve() {
    ll n;
    cin >> n;
    auto calc = [&](ll x) -> ll {
        ll ans = 0;
        for (ll i = 1; i <= x; i *= 10) {
            ll tem = x / (i * 10);
            ll tem2 = (x / i) % 10;
            ll tem3 = x % i;
            ans += tem * i * 45 + tem2 * (tem2 - 1) / 2 * i + tem2 * (tem3 + 1);
        }
        return ans;
    };
    auto calc2 = [&](ll x) -> ll {
        ll ans = 0;
        ll l = 1;
        for (ll i = 1; l <= x; i++) {
            ll tem = min(x, l * 10 - 1);
            ans += (tem - l + 1) * i;
            l *= 10;
        }
        return ans;
    };

    ll l = 1, r = 1e18, mid, ans;
    auto check = [&](ll mid) { return calc2(mid) <= n; };
    while (l <= r) {
        mid = (l + r) / 2;
        if (check(mid)) {
            ans = mid;
            l = mid + 1;
        } else
            r = mid - 1;
    }
    ll res = calc(ans);
    ll re = n - calc2(ans);
    string s = to_string(ans + 1);
    rep(i, 0, re - 1) res += (s[i] - '0');
    cout << res << endl;
    return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

using i128 = __int128_t;
void solve() {
    ll n, m, q, x, y, z;
    cin >> n >> m >> q;
    vl a(n), b(m);
    rep(i, 0, n - 1) cin >> a[i];
    rep(i, 0, m - 1) cin >> b[i];
    sort(all2(a)), sort(all2(b));
    vl pre(n + 1), pre2(m + 1);
    rep(i, 1, n) pre[i] = pre[i - 1] + a[i - 1];
    rep(i, 1, m) pre2[i] = pre2[i - 1] + b[i - 1];
    rep(i, 0, q - 1) {
        cin >> x >> y >> z;
        ll l = max(0LL, z - y);
        ll r = min(x, z) - 1;
        ll mid, ans = l - 1;
        auto check = [&](ll mid) -> bool { return pre[mid] + pre2[z - mid] <= pre[mid + 1] + pre2[z - mid - 1]; };
        while (l <= r) {
            mid = (l + r) / 2;
            if (check(mid)) {
                ans = mid;
                l = mid + 1;
            } else
                r = mid - 1;
        }
        cout << pre[ans + 1] + pre2[z - ans - 1] << endl;
    }
    return;
}

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

using i128 = __int128_t;
struct EBCC {
    int n, m, tim, tot;
    vector<vector<pii>> g;  // {to, edge_id}
    vector<pii> edges;      // edges[id] = {u, v}
    vi dfn, low, is_bridge, bel;
    vvi comps;  // comps[i] 是第 i 个边双里的点

    EBCC(int n = 0) { init(n); }

    void init(int n_) {
        n = n_;
        m = tim = tot = 0;
        g.assign(n, vector<pii>());
        edges.clear();
        dfn.assign(n, 0);
        low.assign(n, 0);
        is_bridge.clear();
        bel.assign(n, -1);
        comps.clear();
    }

    int add_edge(int u, int v) {
        edges.push_back({u, v});
        is_bridge.push_back(0);
        g[u].push_back({v, m});
        g[v].push_back({u, m});
        return m++;
    }

    void tarjan(int u, int pe) {
        dfn[u] = low[u] = ++tim;
        for (int i = 0; i < sz(g[u]); i++) {
            int v = g[u][i].first;
            int id = g[u][i].second;
            if (id == pe) continue;
            if (!dfn[v]) {
                tarjan(v, id);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) is_bridge[id] = 1;
            } else {
                low[u] = min(low[u], dfn[v]);
            }
        }
    }

    void dfs_comp(int u) {
        bel[u] = tot;
        comps.back().push_back(u);
        for (int i = 0; i < sz(g[u]); i++) {
            int v = g[u][i].first;
            int id = g[u][i].second;
            if (bel[v] != -1 || is_bridge[id]) continue;
            dfs_comp(v);
        }
    }

    vi work() {
        rep(i, 0, n - 1) {
            if (!dfn[i]) tarjan(i, -1);
        }
        rep(i, 0, n - 1) {
            if (bel[i] == -1) {
                comps.push_back(vi());
                dfs_comp(i);
                tot++;
            }
        }
        return bel;
    }

    // 建桥树，要求先 work()
    vvi build_tree() {
        vvi tree(tot);
        rep(id, 0, m - 1) {
            if (!is_bridge[id]) continue;
            int a = bel[edges[id].first];
            int b = bel[edges[id].second];
            tree[a].push_back(b);
            tree[b].push_back(a);
        }
        return tree;
    }

    // 建带原图边编号的桥树，tree[u] 中元素为 {v, edge_id}
    vector<vector<pii>> build_tree_with_edge_id() {
        vector<vector<pii>> tree(tot);
        rep(id, 0, m - 1) {
            if (!is_bridge[id]) continue;
            int a = bel[edges[id].first];
            int b = bel[edges[id].second];
            tree[a].push_back({b, id});
            tree[b].push_back({a, id});
        }
        return tree;
    }
};
void solve() {
    ll n, m, x, y, q;
    cin >> n >> m;
    EBCC ebcc(n);
    rep(i, 0, m - 1) {
        cin >> x >> y;
        ebcc.add_edge(x - 1, y - 1);
    }
    vi bel = ebcc.work();
    ll s = bel[0], t = bel[n - 1];
    vector<vector<pii>> tree = ebcc.build_tree_with_edge_id();
    vl vis(m);
    if (s != t) {
        vi pa(ebcc.tot, -1);
        vi pe(ebcc.tot, -1);
        queue<int> qq;
        qq.push(s);
        pa[s] = s;
        while (!qq.empty()) {
            auto node = qq.front();
            qq.pop();
            for (auto& [p, id] : tree[node]) {
                if (pa[p] != -1) continue;
                pa[p] = node;
                pe[p] = id;
                qq.push(p);
            }
        }
        for (int i = t; i != s; i = pa[i]) vis[pe[i]] = 1;
    }
    vl dis(n, LLONG_MAX / 3);
    vl ans(n, LLONG_MAX / 3);
    priority_queue<trl, vector<trl>, greater<>> qq;
    rep(i, 0, m - 1) {
        if (!vis[i]) continue;
        int x = ebcc.edges[i].first, y = ebcc.edges[i].second;
        if (make_pair(0LL, i + 1) < make_pair(dis[x], ans[x])) {
            dis[x] = 0, ans[x] = i + 1, qq.emplace(dis[x], i + 1, x);
        }
        if (make_pair(0LL, i + 1) < make_pair(dis[y], ans[y])) {
            dis[y] = 0, ans[y] = i + 1, qq.emplace(dis[y], i + 1, y);
        }
    }
    while (!qq.empty()) {
        auto [dis_x, id, x] = qq.top();
        qq.pop();
        if (dis_x != dis[x] || id != ans[x]) continue;
        for (auto& [y, id2] : ebcc.g[x]) {
            if (make_pair(dis_x + 1, id) < make_pair(dis[y], ans[y])) {
                dis[y] = dis_x + 1, ans[y] = id;
                qq.emplace(dis[y], ans[y], y);
            }
        }
    }
    cin >> q;
    rep(i, 0, q - 1) {
        cin >> x;
        cout << (dis[x - 1] == LLONG_MAX / 3 ? -1 : ans[x - 1]) << ' ';
    }
    cout << endl;
    return;
}