Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# Author Problem Lang Verdict Time Memory Sent Judged  
128625308 Contestant:
Arthur_Lobo
1566D1 - 39 GNU C++17 Accepted 31 ms 3932 KB 2021-09-12 18:20:28 2021-09-12 22:28:52
 
 
→ Source
#include <bits/stdc++.h>
 
using namespace std;

const long long INFll = (long long) 1e18 + 10;
const int INFii = (int) 1e9 + 10;
typedef long long ll;
typedef int ii;
typedef double dbl;
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

#define maxn 350

ll n, m, bit[maxn];
vector<ll> a, c;

ll cmp(ii x, ii y) {
    if(a[x] != a[y]) {
        return a[x] < a[y];
    }

    return x > y;
}

void att(ii pos, ii val) {
    for(ii i = pos; i <= m; i+= i&-i) {
        bit[i]+= val;
    }
}

ll query(ii pos) {
    ll s = 0;
    for(ii i = pos; i > 0; i-= i&-i) {
        s+= bit[i];
    }
    return s;
}

void solve() {
    a.clear();
    c.clear();
    cin >> n >> m;

    for(ii i = 0; i < m; i++) {
        ll x; cin >> x;
        bit[i] = 0;
        a.pb(x);
        c.pb(i);
    }

    sort(all(c), cmp);

    vector<ll> b;
    for(ii i = 0; i < m; i++) {
        b.pb(c[i]);
    }

    ll ans = 0;
    for(ii i = 0; i < m; i++) {
        // i vai sentar em b[i]

        ans+= query(b[i]);
        att(b[i]+1, +1);
    }

    cout << ans << endl;

}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);

    //freopen("in.in", "r", stdin);
    //freopen(".out", "w", stdout);
 

    ii tt = 1;
    cin >> tt;
    while(tt--) {
        solve();
    }
}
 
 
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details