QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#232986#5507. InvestorssgrcnRE 0ms3816kbC++172.5kb2023-10-31 08:40:122023-10-31 08:40:13

Judging History

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

  • [2023-10-31 08:40:13]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:3816kb
  • [2023-10-31 08:40:12]
  • 提交

answer

#include "bits/stdc++.h"
#include "bits/extc++.h"

using namespace std;
using namespace __gnu_pbds;

#define fwd(i,a,b) for(int i=(a); i<(b);i++)
#define ford(i,a,b) for(int i=(a); i>(b); i--)
#define rep(i,n) fwd(i,0,n)

template<typename T>
using TreeLess = tree <T,  null_type,  greater<T>,  rb_tree_tag,  tree_order_statistics_node_update>;
template<typename T>
using TreeHigh = tree <T,  null_type,  less<T>,  rb_tree_tag,  tree_order_statistics_node_update>;

#define DEBUG

#ifdef DEBUG
template<typename T1, typename T2> auto& operator<<(ostream& out, const pair<T1, T2>& a) { return out << "(" << a.first << ", " << a.second << ")"; }
template<typename T, typename N> auto& operator<<(N& out, const T& a) { out << "{"; for (const auto& b : a) out << b << ", "; return out << "}"; }
template<typename... Args> void print(Args&&... args) { (cerr << ... << args) << "\n"; }
#define debug(x...) cerr << "[" #x "]: ", print(x)
#else
#define debug(...) ;
#endif

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

    int t, n, k, ans, c;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        ans = 0;

        vector<int> D(n);
        vector<vector<int>> S(n, vector<int>(n)), B(n, vector<int>(n));

        rep(i, n) cin >> D[i];
        rep(i, n) {
            c = 0;
            fwd(j, i+1, n) {
                if(D[i] > D[j]) {
                    ans++; c++;
                }
                S[i][j] = c;
            }
            c = 0;
            ford(j, i, -1) {
                if(D[j] > D[i]) c++;
                B[i][j] = c;
            }
            B[i][n-1] = c;
        }

        int sum, maxv, maxi, imin, imax;
        TreeLess<int> dtree;
        TreeHigh<int> utree;
        set<int> skey;
        dtree.insert(-1);
        utree.insert(n-1);
        rep(z, k) {
            maxv = 0;
            sum = 0;
            rep(i, n) {
                sum -= B[i][n-1];
                sum += S[i][n-1];
                if(sum > maxv && !skey.count(i)) {
                    maxi = i;
                    maxv = sum;
                }
            }
            skey.insert(maxi);
            ans -= maxv;

            imin = *dtree.find_by_order(dtree.order_of_key(maxi));
            imax = *utree.find_by_order(utree.order_of_key(maxi+1));
            ford(i, maxi, imin) S[i][n-1] = S[i][maxi];
            fwd(i, maxi+1, imax+1) B[i][n-1] = S[i][maxi+1];
            dtree.insert(maxi); utree.insert(maxi);
        }
        cout << ans << '\n';
    }

    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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
Runtime Error

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:


result: