QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#105721#5507. InvestorsMHJMBSWA 37ms3364kbC++202.2kb2023-05-15 07:40:332023-05-15 07:40:36

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-15 07:40:36]
  • 评测
  • 测评结果:WA
  • 用时:37ms
  • 内存:3364kb
  • [2023-05-15 07:40:33]
  • 提交

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'