编号 题目 状态 分数 总时间 内存 代码 / 答案文件 提交者 提交时间
#5307 #1050. 求和 Accepted 100 66 ms 3716 K C++ 17 / 1.1 K t330026229 2024-04-27 14:27:30
显示原始代码
#include <bits/stdc++.h>
using namespace std;

#define int long long


const int N = 2e5 + 10, T = 1e4 + 10;
int t, n, a[T], d[N], maxm = 0, tr[N];

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') {
        if (c == '-')
            f = -1;
        c = getchar();
    }
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}

int lowbit(int x) { return x & (-x); }

void modify(int x, int k) {
    while (x <= maxm) {
        tr[x] += k;
        x += lowbit(x);
    }
}

int query(int x) {
    int ans = 0LL;
    while (x) {
        ans += tr[x];
        x -= lowbit(x);
    }
    return ans;
}

signed main() {
    t = read();
    for (int i = 1; i <= t; i++) a[i] = read(), maxm = max(maxm, a[i]);
    /*for (int i = 1; i <= maxm; i++) {
            d[i] = d[i - 1] + 1;
            if (i % 10 == 0) d[i] -= 9;
            //modify(i, d[i]);
    }*/
    for (int i = 1; i <= maxm; i++) {
        int m = i;
        while (m) {
            d[i] += (m % 10);
            m /= 10;
        }
        modify(i, d[i]);
    }
    for (int i = 1; i <= t; i++) {
        int oup = query(a[i]);
        printf("%lld\n", oup);
    }
    // for (int i = 1; i <= maxm; i++) printf("%lld ", d[i]);
    return 0;
}
子任务 #1
Accepted
得分:100
测试点 #1
Accepted
得分:100
用时:3 ms
内存:284 KiB

输入文件(1.in

1
8

答案文件(1.out

36

用户输出

36

系统信息

Exited with return code 0
测试点 #2
Accepted
得分:100
用时:3 ms
内存:288 KiB

输入文件(2.in

10
1
6
1
8
3
4
6
9
8
6

答案文件(2.out

1
21
1
36
6
10
21
45
36
21

用户输出

1
21
1
36
6
10
21
45
36
21

系统信息

Exited with return code 0
测试点 #3
Accepted
得分:100
用时:4 ms
内存:740 KiB

输入文件(3.in

5000
4757
4980
4972
4759
4906
4561
4753
4946
4764
4971
4607
4616
4899
4567
4853
4890
4962
4862
4620

<24905 bytes omitted>

答案文件(3.out

72231
77001
76798
72280
75412
68491
72145
76200
72375
76776
69408
69543
75300
68608
74199
75066
7656
<29900 bytes omitted>

用户输出

72231
77001
76798
72280
75412
68491
72145
76200
72375
76776
69408
69543
75300
68608
74199
75066
76560
74397
69612
67555
72444
75
<29872 bytes omitted>

系统信息

Exited with return code 0
测试点 #4
Accepted
得分:100
用时:4 ms
内存:484 KiB

输入文件(4.in

5000
4617
4909
4775
4537
4948
4724
4947
4523
4927
4783
4653
4791
4704
4970
4886
4999
4940
4892
4611

<24905 bytes omitted>

答案文件(4.out

69561
75475
72618
68059
76249
71595
76224
67830
75808
72802
70191
72996
71265
76755
74961
77500
7607
<29900 bytes omitted>

用户输出

69561
75475
72618
68059
76249
71595
76224
67830
75808
72802
70191
72996
71265
76755
74961
77500
76077
75111
69468
73305
69000
69
<29872 bytes omitted>

系统信息

Exited with return code 0
测试点 #5
Accepted
得分:100
用时:3 ms
内存:524 KiB

输入文件(5.in

5000
4735
4595
4746
4560
4716
4716
4918
4990
4656
4809
4759
4613
4608
4750
4899
4517
4970
4553
4944

<24905 bytes omitted>

答案文件(5.out

71794
69198
72006
68475
71460
71460
75637
77257
70251
73365
72280
69495
69426
72091
75300
67743
7675
<29900 bytes omitted>

用户输出

71794
69198
72006
68475
71460
71460
75637
77257
70251
73365
72280
69495
69426
72091
75300
67743
76755
68337
76155
69300
75489
75
<29872 bytes omitted>

系统信息

Exited with return code 0
测试点 #6
Accepted
得分:100
用时:4 ms
内存:492 KiB

输入文件(6.in

5000
4924
4873
4529
4806
4802
4601
4906
4643
4688
4663
4695
4699
4532
4503
4520
4701
4895
4756
4981

<24905 bytes omitted>

答案文件(6.out

75745
74647
67935
73305
73239
69321
75412
70002
70938
70390
71094
71200
67974
67542
67791
71223
7518
<29900 bytes omitted>

用户输出

75745
74647
67935
73305
73239
69321
75412
70002
70938
70390
71094
71200
67974
67542
67791
71223
75186
72208
77023
71200
70453
75
<29872 bytes omitted>

系统信息

Exited with return code 0
测试点 #7
Accepted
得分:100
用时:11 ms
内存:3556 KiB

输入文件(7.in

10000
199818
199603
199854
199533
199525
199711
199660
199974
199532
199840
199748
199523
199930
199
<69906 bytes omitted>

答案文件(7.out

4593303
4585906
4594545
4583499
4583251
4589560
4587751
4598970
4583469
4594051
4590786
4583190
4597
<79900 bytes omitted>

用户输出

4593303
4585906
4594545
4583499
4583251
4589560
4587751
4598970
4583469
4594051
4590786
4583190
4597336
4590003
4594335
4595220

<79872 bytes omitted>

系统信息

Exited with return code 0
测试点 #8
Accepted
得分:100
用时:11 ms
内存:3564 KiB

输入文件(8.in

10000
199547
199674
199831
199997
199807
199967
199574
199707
199834
199811
199644
199817
199775
199
<69906 bytes omitted>

答案文件(8.out

4583952
4588245
4593736
4599909
4592944
4598700
4584870
4589436
4593835
4593072
4587195
4593267
4591
<79900 bytes omitted>

用户输出

4583952
4588245
4593736
4599909
4592944
4598700
4584870
4589436
4593835
4593072
4587195
4593267
4591758
4585527
4599051
4583046

<79872 bytes omitted>

系统信息

Exited with return code 0
测试点 #9
Accepted
得分:100
用时:12 ms
内存:3592 KiB

输入文件(9.in

10000
199599
199630
199637
199657
199536
199861
199917
199605
199844
199573
199661
199653
199713
199
<69906 bytes omitted>

答案文件(9.out

4585800
4586743
4586967
4587643
4583595
4594807
4596885
4585965
4594185
4584835
4587783
4587501
4589
<79900 bytes omitted>

用户输出

4585800
4586743
4586967
4587643
4583595
4594807
4596885
4585965
4594185
4584835
4587783
4587501
4589619
4595646
4592100
4597660

<79872 bytes omitted>

系统信息

Exited with return code 0
测试点 #10
Accepted
得分:100
用时:11 ms
内存:3716 KiB

输入文件(10.in

10000
199855
199529
199769
199507
199775
199909
199718
199930
199672
199707
199816
199890
199712
199
<69906 bytes omitted>

答案文件(10.out

4594582
4583385
4591545
4582720
4591758
4596625
4589784
4597336
4588174
4589436
4593232
4595931
4589
<79900 bytes omitted>

用户输出

4594582
4583385
4591545
4582720
4591758
4596625
4589784
4597336
4588174
4589436
4593232
4595931
4589589
4583283
4597021
4583106

<79872 bytes omitted>

系统信息

Exited with return code 0