QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#127380#5075. Fenwick Tree_skb_#AC ✓21ms4224kbC++14626b2023-07-19 16:37:172023-07-19 16:37:19

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 16:37:19]
  • 评测
  • 测评结果：AC
  • 用时：21ms
  • 内存：4224kb
查看
  • [2023-07-19 16:37:17]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

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

    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        string s; cin >> s;
        vector <int> f(n + 1);
        int ans = 0;
        for (int i = 1; i <= n; ++i) {
            if (s[i - 1] == '1') {
                if (!f[i]) ans++;
                f[i] = 1;
            } else {
                if (f[i] == 1) ans++;
                f[i] = 0; 
            }
            if (f[i]) if (i + (i & -i) <= n) f[i + (i & -i)]++;
        }
        cout << ans << '\n';
    }
}
源文件, 语言: C++14

详细

Test #1:

score: 100
Accepted
time: 1ms
memory: 3428kb

input:

3
5
10110
5
00000
5
11111

output:

3
0
3

result:

ok 3 number(s): "3 0 3"

Test #2:

score: 0
Accepted
time: 3ms
memory: 3444kb

input:

100000
10
0000000000
10
0000000100
10
0000000000
10
1000000000
10
0000010000
10
0000000000
10
0000000000
10
0000000000
10
0100000000
10
0000000000
10
0000000001
10
0000001000
10
0000000000
10
0000000000
10
0000000001
10
0000100000
10
0010000000
10
0000000000
10
0010000000
10
0000000001
10
0000000000...

output:

0
1
0
2
2
0
0
0
2
0
1
2
0
0
1
2
2
0
2
1
0
0
2
2
2
0
2
2
2
0
2
2
0
0
2
2
0
0
2
0
2
2
0
0
0
0
0
0
0
2
2
2
2
0
1
0
2
2
0
2
2
0
2
2
0
1
0
2
0
0
2
2
0
0
0
1
2
0
2
0
0
0
0
2
2
0
0
0
0
0
0
2
0
2
2
0
2
2
2
0
0
0
0
0
0
0
1
0
0
0
2
0
2
0
0
0
2
0
2
0
0
2
0
0
0
1
0
0
1
2
0
0
2
0
2
0
0
2
0
2
0
0
0
2
0
0
2
2
1
0
...

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 13ms
memory: 3448kb

input:

100000
10
0000001010
10
1110010000
10
0100010000
10
0001010011
10
0100001001
10
0010100000
10
0101000000
10
0100110100
10
1000001010
10
1000101001
10
1000000011
10
0000000000
10
0100011001
10
1000100101
10
0110101000
10
1000110100
10
0011100000
10
1001000000
10
0111001100
10
1100000100
10
1100110000...

output:

4
4
4
3
5
4
2
3
6
7
3
0
5
6
6
3
4
4
3
3
4
2
4
0
3
3
2
2
0
4
2
2
2
2
4
4
2
2
5
5
2
3
0
4
2
6
6
3
3
0
4
5
4
2
0
6
4
7
3
0
2
2
2
1
4
2
2
5
3
0
4
0
0
4
5
0
0
2
5
3
2
4
1
0
2
4
3
2
1
2
2
2
4
2
5
3
3
1
2
4
0
0
2
5
4
2
4
0
5
7
5
2
7
3
2
4
4
5
0
3
4
4
2
2
0
4
2
0
4
4
9
2
2
5
6
2
6
4
2
0
5
2
1
2
4
6
6
0
2
1
...

result:

ok 100000 numbers

Test #4:

score: 0
Accepted
time: 21ms
memory: 3552kb

input:

100000
10
0000011010
10
1011001101
10
1010111001
10
1101010010
10
0010011110
10
0100000101
10
1111011011
10
0101110010
10
1111010010
10
0000101011
10
0101111000
10
1000001000
10
1000001110
10
0010111111
10
0000000000
10
1001011010
10
0110011010
10
1101110101
10
1011011011
10
1101011101
10
0001000000...

output:

4
5
7
4
6
4
5
4
5
5
3
4
5
5
0
7
6
3
6
4
2
2
5
0
3
5
5
0
2
6
6
8
7
0
4
6
0
6
6
3
2
5
2
2
2
6
5
3
0
1
0
2
7
6
3
5
4
2
3
2
6
3
6
4
4
6
2
0
2
6
3
4
4
7
4
2
5
2
3
6
2
4
1
2
5
7
4
5
6
2
4
2
3
4
0
4
0
4
2
4
3
4
2
0
4
1
2
6
6
2
3
0
5
2
1
6
6
5
4
0
8
4
6
3
4
2
5
2
5
5
3
4
4
6
6
2
4
6
4
4
4
0
4
5
2
7
9
7
3
5
...

result:

ok 100000 numbers

Test #5:

score: 0
Accepted
time: 6ms
memory: 3524kb

input:

10000
100
0000000000000000000000010000000000100001000000000000000001010000100000000000000000000000000000100000
100
0001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000
100
01000101000000000000000000000000000001000000010000000000000000000000000000000000...

output:

12
4
10
4
4
8
4
17
2
14
11
18
2
6
4
12
10
2
4
8
8
10
11
4
9
10
18
11
6
10
16
9
8
10
8
2
0
2
0
6
10
10
13
6
16
8
6
14
4
0
0
16
8
6
13
4
0
10
8
10
20
10
6
14
8
14
14
10
16
0
4
8
13
14
17
8
4
16
8
12
10
14
6
4
4
4
10
10
5
11
18
8
14
0
18
8
15
4
10
4
13
16
12
18
0
18
6
16
8
7
16
10
8
17
14
4
2
10
16
6
1...

result:

ok 10000 numbers

Test #6:

score: 0
Accepted
time: 7ms
memory: 3516kb

input:

10000
100
0000101000000010000001000010000010001000010101000100000000010010000100000000001001000001010010001000
100
1010100000100000111000100000000000010000000000101011100000000001000000000000001001000101000010000000
100
00000000000000000000000000000000000000000000000000000000000000000000000000000010...

output:

34
31
2
24
28
25
4
47
12
20
39
32
11
31
37
44
22
29
35
20
31
16
15
31
23
24
10
33
35
25
37
25
37
35
17
38
32
26
39
36
24
39
41
18
37
6
46
8
25
34
12
33
16
15
29
33
38
35
39
6
13
22
34
28
38
23
6
23
36
14
30
31
33
13
9
47
35
42
40
25
23
40
33
18
17
8
39
8
23
35
8
34
41
34
30
20
35
20
25
45
22
30
34
2...

result:

ok 10000 numbers

Test #7:

score: 0
Accepted
time: 4ms
memory: 3460kb

input:

10000
100
0011000101011111100110001000100000011110100011101010010000110011010011110001111110000110100100001001
100
0010000000000000000001000000000000000000000000001000100000000000000000000000000000000000000000000010
100
10101011110111011010111101100110101011111111111110111010110101111011100011101110...

output:

47
10
55
48
37
45
27
50
52
12
41
36
25
32
43
49
26
16
42
47
6
42
44
39
8
45
46
52
39
34
19
37
47
48
50
13
37
48
46
14
23
39
37
40
46
45
8
44
39
24
21
45
35
25
27
44
31
57
14
57
43
31
41
36
34
42
53
46
37
40
38
31
44
42
54
4
6
31
21
46
51
38
44
50
41
2
39
50
41
34
42
44
35
34
48
7
31
52
10
39
44
34
6...

result:

ok 10000 numbers

Test #8:

score: 0
Accepted
time: 5ms
memory: 3464kb

input:

1000
1000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
110
122
105
92
50
34
139
90
62
22
100
64
92
130
4
57
120
2
13
134
58
55
102
148
64
154
143
40
26
90
89
114
2
40
126
137
70
92
12
16
70
73
139
2
20
150
88
123
34
36
78
124
58
10
65
0
120
97
96
144
20
108
132
130
98
84
64
93
146
42
130
0
95
20
60
176
128
44
120
0
99
148
74
62
65
42
64
169
155
4
120
...

result:

ok 1000 numbers

Test #9:

score: 0
Accepted
time: 6ms
memory: 3492kb

input:

1000
1000
00011111000010001011010010000010101011110011001000001010000001010011000100111000000000010000001011000101000000100001010000000011011000010100110000101100010000110010000010010100100100010001010110000000110110100100100010000111000010110111100000010001111000100000011010010000101001011110011010...

output:

381
329
210
362
281
260
306
358
348
415
384
360
357
403
395
44
169
359
369
315
280
316
258
30
260
140
404
203
96
392
160
394
362
376
374
349
172
399
407
65
157
28
40
179
336
372
316
279
251
80
251
218
346
391
382
383
368
189
395
84
253
68
331
376
218
287
226
82
149
246
380
419
336
42
247
404
271
132...

result:

ok 1000 numbers

Test #10:

score: 0
Accepted
time: 7ms
memory: 3520kb

input:

1000
1000
00100001010000111001111101011111110111110000100110111010111111101110101010110100001111100011101001110100100110010000110110111101000011111100001110000010111111011011011011111001000101100010000100000010111111101010111110101110110110111001111000100011000010010010111001111110000101001000100111...

output:

467
436
171
481
487
246
245
415
470
393
455
470
382
416
6
460
438
156
416
484
260
404
396
298
52
365
110
38
254
448
159
28
434
436
376
349
467
466
10
398
408
14
197
311
411
465
8
300
452
159
381
130
243
457
395
257
465
453
40
278
400
435
474
444
240
416
439
416
464
324
447
431
179
478
428
285
334
30...

result:

ok 1000 numbers

Test #11:

score: 0
Accepted
time: 1ms
memory: 3632kb

input:

100
10000
00000001000000000101000000000000000000000000000000001000000000000000000000000010000000000010000000000000000001000001000000000010000000000100000000000000000000000000000000000000000100010000010000000010000100000001000000000000000100000000000000000010000000000000000000001001000000000001100000...

output:

1483
1213
2
1045
691
1363
1282
1495
1183
821
825
813
90
964
633
1475
1527
920
152
364
263
292
118
228
453
1113
134
361
1571
1435
1443
746
964
1600
868
954
714
1393
1271
1277
1477
949
1516
1059
607
286
482
792
1278
114
887
519
1344
1433
425
1415
394
893
198
618
1144
605
1275
1555
548
536
576
971
987
...

result:

ok 100 numbers

Test #12:

score: 0
Accepted
time: 6ms
memory: 3636kb

input:

100
10000
00011000000010000101001110011000100001100110111000101100011010010010000011000010111010000111100000101010010100100000000000000000001000010100010000000110010000001101000000101110110010000011001000001010010001000000010000100100100101001000101101010001001000000100011010110000100000000001000100...

output:

3535
2671
3555
1183
3730
2432
3376
564
231
3769
3164
2570
2170
3588
1720
649
716
3749
2360
3185
130
3984
3193
3338
3827
2806
3880
2198
3808
3759
2313
1462
1345
4105
2849
1038
2287
3037
671
1796
1258
1621
2204
719
3302
2069
3419
3804
1270
3972
3130
3704
2530
3873
252
525
1693
3568
1561
2570
1014
2751...

result:

ok 100 numbers

Test #13:

score: 0
Accepted
time: 7ms
memory: 3560kb

input:

100
10000
00011111111100111100101101111111111101011000101000011111111101110011000110101111110010111100111110011110110001100100011001101110101101011110111011111000011100011010011011101011000110111011111000010110110001110001111110111010111101100010011001111111101001011011111011111100011111011110100001...

output:

4754
4000
3780
4647
4238
4515
4592
4554
1744
4090
3945
4592
2748
4414
4635
2256
1692
4438
2935
1410
4375
3001
3710
3475
4309
3242
4329
4692
3924
2517
3541
4078
947
4458
4621
4312
744
2983
261
4561
3130
4574
3499
3549
3239
1083
1051
1742
4336
2999
4138
3837
4710
3758
4534
2874
4479
4086
1439
3405
457...

result:

ok 100 numbers

Test #14:

score: 0
Accepted
time: 4ms
memory: 4208kb

input:

10
100000
00000000000000000000000000000000000000000000000001000001000000000000000000000010000000000000000101010000000000000000000000100000000001000000001000000000000000010001000000000010000101000100000000000000000000000000000000000000000001000000000011000000000000000000000000000000000000000000000000...

output:

8584
4084
1746
964
8834
711
5993
6493
3835
1710

result:

ok 10 numbers

Test #15:

score: 0
Accepted
time: 5ms
memory: 4172kb

input:

10
100000
00000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001001000000000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

3334
2611
9369
10529
14744
12414
340
14662
14868
3104

result:

ok 10 numbers

Test #16:

score: 0
Accepted
time: 4ms
memory: 4208kb

input:

10
100000
00000000000000010000000100000000000000001010000000000000000100000000110001000001100000001000000000001000000010000000000000000010010000001000000000000100001100000010000000011000010100010000011000000000000000010100010101000000000000001000000100010010000000001000000001001010000001000000000000...

output:

22727
36918
38266
39589
17491
22464
31990
11824
37582
39861

result:

ok 10 numbers

Test #17:

score: 0
Accepted
time: 4ms
memory: 4224kb

input:

10
100000
10000001100000100000000000000001000110110000110011000100000000000000000000000000000101001000000001000000000000100001010000000000101000000010001001001000010000000000100010000001000000000100000110010100001010000100010010001001100100000100000010000100000000000000000000000001010000000000010001...

output:

24511
28732
3286
43353
39312
23907
14861
29009
45012
41944

result:

ok 10 numbers

Test #18:

score: 0
Accepted
time: 4ms
memory: 4212kb

input:

10
100000
00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...

output:

0
0
0
0
0
0
0
0
0
0

result:

ok 10 numbers

Test #19:

score: 0
Accepted
time: 5ms
memory: 4224kb

input:

10
100000
11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111...

output:

50000
50000
50000
50000
50000
50000
50000
50000
50000
50000

result:

ok 10 numbers
English 繁體中文 简体中文

服务器时间: 2024-12-02 19:39:20 | 开源项目