QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#233719	#5507. Investors	sgrcn	WA	2ms	3644kb	C++17	2.4kb	2023-10-31 21:45:50	2023-10-31 21:45:50

Judging History

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

[2023-10-31 21:45:50]
评测

测评结果：WA
用时：2ms
内存：3644kb

查看

[2023-10-31 21:45:50]
提交

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, c;
    cin >> t;
    while(t--) {
        cin >> n >> k;
        vector<int> D(n), PL(n, 0), PR(n, n-1);
        rep(i,n) cin >> D[i];
        vector<vector<int>> L, R;
        L = R = vector<vector<int>>(n, vector<int>(n));
        rep(i,n) {
            c = 0;
            fwd(j, i, n) {
                if(D[i]>D[j]) c++;
                R[i][j] = c;
            }
            c = 0;
            ford(j, i, -1) {
                if(D[i]<D[j]) c++;
                L[i][j] = c;
            }
        }

        TreeHigh<int> thigh; thigh.insert(n-1);
        TreeLess<int> tlow; tlow.insert(-1);

        rep(z, k) {
            int maxv = 0, maxi, acc = 0, l, r;
            rep(i, n) {
                acc += R[i][PR[i]];
                acc -= L[i][PL[i]];
                if(acc>maxv) {
                    maxi = i;
                    maxv = acc;
                }
            }
            l = *tlow.find_by_order(tlow.order_of_key(maxi-1));
            r = *thigh.find_by_order(thigh.order_of_key(maxi+1));
            fwd(i,maxi+1,r+1) PL[i] = maxi+1;
            ford(i,maxi,l) PR[i] = maxi;
        }
        int ansl = 0, ansr = 0;
        rep(i,n) {
            ansl += L[i][PL[i]];
            ansr += R[i][PR[i]];
        }
        cout << min(ansl, ansr) << '\n';
    }

    return 0;
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 0ms

memory: 3644kb

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: 2ms

memory: 3620kb

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:

wrong answer 2nd lines differ - expected: '18', found: '118'