QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#105721 | #5507. Investors | MHJMBS | WA | 37ms | 3364kb | C++20 | 2.2kb | 2023-05-15 07:40:33 | 2023-05-15 07:40:36 |
Judging History
answer
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define fastio ios::sync_with_stdio(0), cin.tie(nullptr)
using namespace std;
using namespace __gnu_pbds;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using tiii = tuple<int,int,int>;
typedef tree<ll,null_type,less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> multiordered_set;
int main() {
fastio;
int t;
cin >> t;
while(t--) {
int n, k;
cin >> n >> k;
vector<ll> a(n);
for(ll &ai : a) cin >> ai;
// {
// multiordered_set ms;
// map<ll,int> occur;
// ll ans = 0;
// for(int i = 0; i < n; i++) {
// ans += i - ms.order_of_key(a[i]) - occur[a[i]];
// ms.insert(a[i]);
// occur[a[i]]++;
// }
// cout << ans << '\n';
// }
while(k--) {
vector<int> dp(n+1, 0);
pll ans = {0,n};
multiordered_set msa, msd;
map<ll,int> occur_a;
for(int i = 0; i < n; i++) {
msa.insert(a[i]);
occur_a[a[i]]++;
}
for(int i = n-1; i >= 0; i--) {
int menores_depois = msd.order_of_key(a[i]);
msd.insert(a[i]);
int maiores_antes = msa.size() - msa.order_of_key(a[i]) - occur_a[a[i]];
msa.erase(msa.upper_bound(a[i]));
occur_a[a[i]]--;
dp[i] = dp[i+1] + maiores_antes - menores_depois;
ans = max(ans, {dp[i],i});
}
// for(int i = 0; i < n; i++) cout << dp[i] << ' ';
// cout << '\n';
for(int i = ans.second; i < n; i++) a[i] += ll(1e10);
}
multiordered_set ms;
map<ll,int> occur;
ll ans = 0;
for(int i = 0; i < n; i++) {
ans += i - ms.order_of_key(a[i]) - occur[a[i]];
ms.insert(a[i]);
occur[a[i]]++;
}
cout << ans << '\n';
}
}
详细
Test #1:
score: 100
Accepted
time: 2ms
memory: 3356kb
input:
2 6 1 4 5 6 2 2 1 6 2 4 5 6 2 2 1
output:
2 0
result:
ok 2 lines
Test #2:
score: -100
Wrong Answer
time: 37ms
memory: 3364kb
input:
349 6 2 2 1 2 1 2 1 48 12 42 47 39 39 27 25 22 44 45 13 5 48 38 4 37 6 24 10 42 38 12 37 31 19 44 6 29 17 7 12 7 26 35 24 15 9 37 3 27 21 33 29 34 20 14 30 31 21 48 12 1 43 17 46 17 39 40 22 25 2 22 12 4 11 38 12 4 11 1 5 39 44 37 10 19 20 42 45 2 45 37 20 48 34 16 41 23 18 13 44 47 21 29 4 23 18 16...
output:
1 18 15 145 0 2 1 0 14 13 24 0 0 0 1 0 0 0 0 0 0 0 0 161 3 0 0 1 0 0 0 0 0 0 1 0 3 0 0 1 0 0 1 0 0 1 4 0 0 0 0 0 0 0 0 2 0 2 0 0 8 280 0 0 35 4 0 1 0 0 3 0 0 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 3 0 0 0 2 0 0 0 0 0 0 0 8 1 10 0 0 0 0 1 11 5 0 0 0 6 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 13 1 0 0 0...
result:
wrong answer 9th lines differ - expected: '13', found: '14'