QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#331286#8052. Dot Productucup-team2000#AC ✓125ms18768kbC++201.5kb2024-02-18 04:30:502024-02-18 04:30:50

Judging History

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

  • [2024-02-18 04:30:50]
  • 评测
  • 测评结果:AC
  • 用时:125ms
  • 内存:18768kb
  • [2024-02-18 04:30:50]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lep(i,a,b) for(int i=(a); i<=(b);i++)
#define rep(i,a,b) for (int i = (a); i >= b; i--)

const int inf = 1e18 + 5;


void solve() {
    int n;
    cin >> n;
    vector<int> pos(n+1);
    vector<int> a(n+1);
    vector<int> bit(n+1);
    auto add = [&](int pos, int delta) -> void {
        for (int i = pos; i <= n; i += i&-i) {
            bit[i] += delta;
        }
    };
    auto get = [&](int pos) -> int {
        int res = 0;
        for (int i = pos; i > 0; i -= i&-i) {
            res += bit[i];
        }
        return res;
    };
    lep(i,1,n) {
        cin >> a[i];
        pos[a[i]] = i;
    }
    vector<int> dp(n+1, inf);
    lep(i,1,n) {
        add(i,+1);
        dp[0] = 0;
    }
    lep(i,0,n-1) {
        // update dp[i+1]
        if (i > 0) add(pos[i], -1);
        int pos_ip1 = get(pos[i+1]);
        dp[i+1] = min(dp[i+1], dp[i] + (pos_ip1 - 1));
        if (i <= n - 2) {
            // update dp[i+2], assume we swap stuff
            int pos_ip2 = get(pos[i+2]);
            int cst = (pos_ip2 - 1);
            if (pos_ip1 > 1) cst += (pos_ip1-2+(pos[i+2]>pos[i+1]));
            dp[i+2] = min(dp[i+2], dp[i] + cst);
        }
    }
    // cout << "dp: \n";
    // lep(i,1,n) {
    //     cout << dp[i] << " ";
    // }
    // cout << "\n";
    cout << dp[n] << "\n";
}

signed main() {
    int t; cin >> t;
    while (t--) solve();
}

这程序好像有点Bug,我给组数据试试?

詳細信息

Test #1:

score: 100
Accepted
time: 0ms
memory: 3584kb

input:

4
3
3 1 2
4
4 3 2 1
5
2 1 5 4 3
1
1

output:

1
4
2
0

result:

ok 4 number(s): "1 4 2 0"

Test #2:

score: 0
Accepted
time: 115ms
memory: 3504kb

input:

100000
4
3 4 2 1
5
5 4 1 3 2
4
3 1 4 2
4
4 2 1 3
4
1 3 2 4
4
4 2 3 1
4
3 2 1 4
5
1 2 3 4 5
5
5 2 3 1 4
5
1 3 5 4 2
5
4 3 2 1 5
5
3 4 2 1 5
5
5 4 3 2 1
4
3 4 2 1
5
4 2 5 1 3
5
4 1 5 2 3
4
3 4 1 2
4
2 1 3 4
5
4 3 2 5 1
4
4 2 1 3
5
3 1 5 2 4
4
4 1 2 3
5
1 5 2 4 3
5
4 1 3 5 2
5
4 2 3 5 1
5
1 2 3 4 5
5
4...

output:

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

result:

ok 100000 numbers

Test #3:

score: 0
Accepted
time: 67ms
memory: 3584kb

input:

62500
7
1 2 4 3 6 5 7
7
7 3 2 1 6 5 4
7
3 5 4 6 7 1 2
8
4 2 1 8 3 6 7 5
8
8 4 6 1 3 5 7 2
7
1 6 4 3 2 5 7
8
2 1 3 5 7 4 8 6
8
8 2 4 1 6 3 5 7
7
1 7 5 6 4 2 3
7
3 2 1 7 4 5 6
7
7 5 3 4 1 6 2
7
2 5 3 1 4 7 6
8
4 1 6 5 8 7 3 2
7
2 1 5 4 7 3 6
8
4 2 8 1 7 5 6 3
8
2 1 6 5 4 3 8 7
7
6 3 5 4 7 2 1
8
8 5 6 ...

output:

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

result:

ok 62500 numbers

Test #4:

score: 0
Accepted
time: 64ms
memory: 3752kb

input:

50000
10
3 1 2 10 6 8 5 4 7 9
10
8 3 9 2 10 4 5 1 7 6
9
6 8 4 9 5 7 1 3 2
9
6 7 9 3 8 5 2 1 4
10
7 10 1 2 6 5 3 9 4 8
10
1 10 4 3 2 9 7 8 5 6
9
1 5 3 4 9 6 7 2 8
10
4 7 2 8 3 6 9 5 10 1
9
6 4 9 1 8 5 2 3 7
10
5 1 7 8 10 3 9 6 2 4
9
4 8 6 3 9 7 5 2 1
9
9 1 7 6 2 3 8 5 4
10
5 7 2 1 4 3 6 8 9 10
10
9 7...

output:

10
22
23
23
18
16
8
17
17
19
21
17
8
22
19
19
9
17
32
12
19
28
9
20
21
27
10
9
17
13
20
18
17
22
26
25
20
19
9
19
26
12
14
7
14
24
19
9
16
16
24
18
18
23
15
30
16
9
25
23
16
23
10
16
13
21
20
21
26
21
26
20
6
25
14
22
22
16
14
23
12
18
24
20
12
14
12
11
16
23
15
6
19
15
22
13
15
13
17
13
14
22
12
13...

result:

ok 50000 numbers

Test #5:

score: 0
Accepted
time: 56ms
memory: 3804kb

input:

5000
94
69 86 59 9 67 89 24 63 14 18 16 11 19 46 23 40 4 55 53 61 30 3 78 29 15 74 32 41 51 13 77 47 66 92 57 45 42 21 62 43 26 1 84 75 71 54 73 36 39 48 88 8 80 64 58 10 60 76 17 70 25 37 38 6 72 91 7 20 68 2 35 44 90 79 50 93 81 94 27 33 5 52 28 82 56 87 31 22 83 34 65 85 49 12
97
44 97 28 56 95 6...

output:

1959
2580
1998
2158
2176
2196
1976
2170
1856
2130
2056
1864
1802
2138
1898
1902
2465
2442
2180
2505
2281
2135
2441
2570
2376
2448
2296
2393
1926
2064
2341
2473
2031
2289
2063
2202
2113
2580
1787
2106
2000
2462
1784
1789
2260
1934
2117
2344
2428
2210
2157
2115
2343
2548
2493
2161
2079
2284
2310
2099
...

result:

ok 5000 numbers

Test #6:

score: 0
Accepted
time: 69ms
memory: 3620kb

input:

500
959
670 618 579 212 780 557 380 412 672 951 777 921 684 768 99 952 140 122 139 919 623 17 911 18 880 790 625 505 307 747 801 754 783 146 757 263 285 228 719 640 199 193 105 234 847 842 348 159 823 577 466 954 850 851 643 802 819 317 826 55 617 690 604 229 570 254 759 575 498 240 397 736 864 415 ...

output:

228796
197927
207066
195802
234013
226390
227806
210077
222517
210911
235915
243652
239088
221085
239815
232724
229159
225962
246468
225698
247998
194708
235417
237194
205416
231487
206280
207787
216193
224206
242111
223196
209206
245074
211845
228906
246116
249415
241752
215609
206190
221459
222390...

result:

ok 500 numbers

Test #7:

score: 0
Accepted
time: 77ms
memory: 3884kb

input:

50
9597
2421 5801 7761 5556 4158 3033 4751 9284 3326 1858 2849 8472 5917 6077 4438 1948 5294 3028 4716 8042 2671 5305 5076 6924 5569 8173 6362 2160 3095 7385 1374 3167 8128 551 2363 1371 5799 3273 1366 5050 7680 198 5577 1236 2843 1127 5381 3029 6977 4823 702 8077 528 526 7027 4278 7947 6058 5005 90...

output:

23041936
20791070
20560711
20793660
23672434
20769348
23972180
22642287
22305166
22772174
23928405
22017477
24064164
23093739
24522067
20357382
24328268
21899881
20915966
21115138
20908959
21284093
22950774
20384100
21102605
23636118
21279692
21578304
22894986
24522463
22167550
23372016
22250714
204...

result:

ok 50 numbers

Test #8:

score: 0
Accepted
time: 99ms
memory: 6228kb

input:

5
92316
4486 51971 40435 31486 22840 51804 19355 35116 71427 50525 34461 46690 44101 15605 33166 25846 90319 50846 8819 36285 58519 23478 20717 14434 37378 37454 60063 17182 70164 59883 45000 84942 58799 11505 13371 52739 66680 30438 67677 41266 53940 34428 79533 55092 76616 54423 21642 25614 48002 ...

output:

2135607119
2495202510
2408080975
2151285466
2323263800

result:

ok 5 number(s): "2135607119 2495202510 2408080975 2151285466 2323263800"

Test #9:

score: 0
Accepted
time: 120ms
memory: 17860kb

input:

1
471631
424496 112701 456051 347801 218724 312785 85999 325031 220919 219326 327801 239646 431816 121964 216653 223784 147176 29672 466026 412872 269415 238525 365823 442104 346534 297299 298496 242174 296754 297691 105566 80641 204310 21696 170588 199258 59123 336907 57422 387873 209433 272911 261...

output:

55601147812

result:

ok 1 number(s): "55601147812"

Test #10:

score: 0
Accepted
time: 117ms
memory: 3588kb

input:

100000
5
1 4 2 3 5
5
5 1 3 4 2
5
3 2 4 1 5
5
1 4 5 3 2
5
5 2 3 4 1
5
5 4 2 1 3
5
5 1 2 4 3
5
4 5 3 1 2
5
2 4 5 1 3
5
1 2 4 3 5
5
1 5 2 3 4
5
5 2 3 1 4
5
3 1 2 4 5
5
1 3 2 4 5
5
4 3 2 1 5
5
1 4 3 2 5
5
2 5 4 1 3
5
5 4 3 2 1
5
4 1 5 3 2
5
3 1 2 5 4
5
2 4 5 1 3
5
2 1 3 4 5
5
5 2 3 4 1
5
5 4 2 3 1
5
2 1...

output:

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

result:

ok 100000 numbers

Test #11:

score: 0
Accepted
time: 102ms
memory: 6340kb

input:

5
100000
56449 21738 74917 44834 36187 96576 37204 28451 3444 13029 66039 8955 51445 30706 27229 37159 66052 16691 70389 29935 44984 3648 75082 73600 76621 28345 5298 37940 49412 85260 92029 18185 84398 10233 79227 98312 96649 30680 65206 38879 75397 26951 11294 58085 37297 97167 59252 44104 4058 37...

output:

2501939630
2497324750
2494452786
2503094933
2490340697

result:

ok 5 number(s): "2501939630 2497324750 2494452786 2503094933 2490340697"

Test #12:

score: 0
Accepted
time: 125ms
memory: 18768kb

input:

1
500000
424496 175348 456051 347801 218724 312785 90971 325031 220919 219326 327801 239646 431816 92753 216653 223784 12744 57478 466026 412872 269415 238525 365823 442104 346534 297299 298496 242174 296754 297691 89046 132550 204310 59418 121482 199258 47499 336907 151917 387873 209433 272911 2611...

output:

62502680693

result:

ok 1 number(s): "62502680693"

Extra Test:

score: 0
Extra Test Passed