QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#672761 | #8052. Dot Product | lonelywolf# | AC ✓ | 80ms | 22760kb | C++20 | 1.7kb | 2024-10-24 18:48:39 | 2024-10-24 18:48:39 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
template <typename T>
struct Fenwick {
int n;
vector<T> a;
Fenwick(int n_ = 0) {
init(n_);
}
void init(int n_) {
n = n_;
a.assign(n + 1, T{});
}
void add(int x, const T &v) {
for (int i = x; i <= n; i += i & -i) {
a[i] = a[i] + v;
}
}
T sum(int x) {
T ans{};
for (int i = x; i > 0; i -= i & -i) {
ans = ans + a[i];
}
return ans;
}
T rangeSum(int l, int r) {
return sum(r) - sum(l - 1);
}
// 权值树状数组,查询第k小
int select(const T &k) {
int x = 0;
T cur{};
for (int i = 1 << __lg(n); i; i /= 2) {
if (x + i < n && cur + a[x + i] < k) {
x += i;
cur = cur + a[x];
}
}
return x + 1;
}
};
void solve() {
int n;
cin >> n;
vector<int> a(n + 1), p(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
p[a[i]] = i;
}
Fenwick<int> f(n);
vector<int> v(n + 1);
for (int i = 1; i <= n; i++) {
f.add(a[i], 1);
int s = f.sum(a[i]);
v[a[i]] = i - s;
}
vector<int> dp(n + 1, 1e18);
dp[0] = 0;
for (int i = 1; i <= n; i++) {
dp[i] = dp[i - 1] + v[i];
if (i >= 2) {
int x = dp[i - 2] + v[i - 1] + v[i];
if (p[i - 1] > p[i]) {
x--;
}
dp[i] = min(dp[i], x);
}
}
cout << dp[n] << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int t;
cin >> t;
while (t--) {
solve();
}
return 0;
}
这程序好像有点Bug,我给组数据试试?
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3800kb
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: 32ms
memory: 3632kb
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: 30ms
memory: 3536kb
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: 30ms
memory: 3592kb
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: 21ms
memory: 3836kb
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: 24ms
memory: 3572kb
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: 30ms
memory: 3616kb
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: 37ms
memory: 7060kb
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: 47ms
memory: 21576kb
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: 33ms
memory: 3548kb
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: 43ms
memory: 7076kb
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: 80ms
memory: 22760kb
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