Ideone.com

fork download

copy

#include <bits/stdc++.h>
 
#define FILENAME "MAIN"
#define ll long long 
#define el cout << '\n'
#define ii pair<ll, ll>
#define fi first 
#define se second 
#define pb push_back
#define YES cout << "YES", el
#define NO cout << "NO", el
#define print_type cout
#define print_el print_type << '\n'
#define DEBUG(...) [](auto && ... x) {int i = 0; ((print_type << (i++ ? " " : "") << x), ...), print_el;} (__VA_ARGS__)
#define bit(mask, i) (((mask) >> (i)) & 1)
#define BIT(n) (1ll << (n))
 
using namespace std;
 
const bool is_brute = 0;
const bool multi_test = 1;
 
const int maxn = 1e6;
const int INF = 1e9;
 
struct FenwickTree
{
    int maxn;
    vector<int> bit;
 
    FenwickTree() {};
    FenwickTree(int maxn) : maxn(maxn)
    {
        bit.assign(maxn + 10, 0);
    }
    void update(int x, int val)
    {
        for (; x <= maxn; x += x &- x)
            bit[x] += val;
    }
    int get(int x)
    {
        int ans = 0;
        for (; x; x &= x - 1)
            ans += bit[x];
        return ans;
    }
    int getPrefix(int x)
    {
        return get(x);
    }
    int getSuffix(int x)
    {
        return get(maxn) - get(x - 1);
    }
};
 
int n, m, a[maxn + 10], b[maxn + 10];
ll ans = 0;
FenwickTree treePrefix, treeSuffix;
vector<int> val;
 
int getID(int x)
{
    return lower_bound(val.begin(), val.end(), x) - val.begin() + 1;
}
void dnc(int l, int r, int optl, int optr)
{
    if (r < l)
        return ;
    int m = l + r >> 1;
    ii best = ii(INF, INF);
    for (int i = optl; i <= optr; i++)
    {
        treeSuffix.update(a[i], -1);
        treePrefix.update(a[i], 1);
        best = min(best, ii(treePrefix.getSuffix(b[m] + 1) + treeSuffix.getPrefix(b[m] - 1), i));
    }
    ans += best.fi;
    for (int i = optl; i <= optr; i++)
    {
        treePrefix.update(a[i], -1);
        treeSuffix.update(a[i], 1);
    }
    dnc(l, m - 1, optl, best.se);
    for (int i = optl; i <= best.se - 1; i++)
    {
        treePrefix.update(a[i], 1);
        treeSuffix.update(a[i], -1);
    }
    dnc(m + 1, r, best.se, optr);
    for (int i = optl; i <= best.se - 1; i++)
    {
        treePrefix.update(a[i], -1);
        treeSuffix.update(a[i], 1);
    }
}
 
void solve()
{
    ans = 0;
    cin >> n >> m;
    val.clear();
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        val.push_back(a[i]);
    }
    for (int i = 1; i <= m; i++)
    {
        cin >> b[i];
        val.push_back(b[i]);
    }
    val.push_back(0);
    sort(val.begin(), val.end());
    val.resize(unique(val.begin(), val.end()) - val.begin());
    sort(b + 1, b + m + 1);
    a[0] = 0;
    for (int i = 0; i <= n; i++)
        a[i] = getID(a[i]);
    for (int i = 1; i <= m; i++)
        b[i] = getID(b[i]);
    treePrefix = treeSuffix = FenwickTree(val.size());
    for (int i = 0; i <= n; i++)
    {
        ans += treeSuffix.getSuffix(a[i] + 1);
        treeSuffix.update(a[i], 1);
    }
    dnc(1, m, 0, n);
    cout << ans, el;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    if (fopen(FILENAME".INP", "r"))
    {
        freopen(FILENAME".INP", "r", stdin);
        if (is_brute)
            freopen(FILENAME"_TRAU.OUT", "w", stdout);
        else
            freopen(FILENAME".OUT", "w", stdout);
    }
 
    int ntest;
    if (multi_test)
        cin >> ntest;
    else
        ntest = 1;
    for (int itest = 1; itest <= ntest; itest++)
    {
        // cout << itest, el;
        solve();
    }
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CgojZGVmaW5lIEZJTEVOQU1FICJNQUlOIgojZGVmaW5lIGxsIGxvbmcgbG9uZyAKI2RlZmluZSBlbCBjb3V0IDw8ICdcbicKI2RlZmluZSBpaSBwYWlyPGxsLCBsbD4KI2RlZmluZSBmaSBmaXJzdCAKI2RlZmluZSBzZSBzZWNvbmQgCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgWUVTIGNvdXQgPDwgIllFUyIsIGVsCiNkZWZpbmUgTk8gY291dCA8PCAiTk8iLCBlbAojZGVmaW5lIHByaW50X3R5cGUgY291dAojZGVmaW5lIHByaW50X2VsIHByaW50X3R5cGUgPDwgJ1xuJwojZGVmaW5lIERFQlVHKC4uLikgW10oYXV0byAmJiAuLi4geCkge2ludCBpID0gMDsgKChwcmludF90eXBlIDw8IChpKysgPyAiICIgOiAiIikgPDwgeCksIC4uLiksIHByaW50X2VsO30gKF9fVkFfQVJHU19fKQojZGVmaW5lIGJpdChtYXNrLCBpKSAoKChtYXNrKSA+PiAoaSkpICYgMSkKI2RlZmluZSBCSVQobikgKDFsbCA8PCAobikpCgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgYm9vbCBpc19icnV0ZSA9IDA7CmNvbnN0IGJvb2wgbXVsdGlfdGVzdCA9IDE7Cgpjb25zdCBpbnQgbWF4biA9IDFlNjsKY29uc3QgaW50IElORiA9IDFlOTsKCnN0cnVjdCBGZW53aWNrVHJlZQp7CiAgICBpbnQgbWF4bjsKICAgIHZlY3RvcjxpbnQ+IGJpdDsKCiAgICBGZW53aWNrVHJlZSgpIHt9OwogICAgRmVud2lja1RyZWUoaW50IG1heG4pIDogbWF4bihtYXhuKQogICAgewogICAgICAgIGJpdC5hc3NpZ24obWF4biArIDEwLCAwKTsKICAgIH0KICAgIHZvaWQgdXBkYXRlKGludCB4LCBpbnQgdmFsKQogICAgewogICAgICAgIGZvciAoOyB4IDw9IG1heG47IHggKz0geCAmLSB4KQogICAgICAgICAgICBiaXRbeF0gKz0gdmFsOwogICAgfQogICAgaW50IGdldChpbnQgeCkKICAgIHsKICAgICAgICBpbnQgYW5zID0gMDsKICAgICAgICBmb3IgKDsgeDsgeCAmPSB4IC0gMSkKICAgICAgICAgICAgYW5zICs9IGJpdFt4XTsKICAgICAgICByZXR1cm4gYW5zOwogICAgfQogICAgaW50IGdldFByZWZpeChpbnQgeCkKICAgIHsKICAgICAgICByZXR1cm4gZ2V0KHgpOwogICAgfQogICAgaW50IGdldFN1ZmZpeChpbnQgeCkKICAgIHsKICAgICAgICByZXR1cm4gZ2V0KG1heG4pIC0gZ2V0KHggLSAxKTsKICAgIH0KfTsKCmludCBuLCBtLCBhW21heG4gKyAxMF0sIGJbbWF4biArIDEwXTsKbGwgYW5zID0gMDsKRmVud2lja1RyZWUgdHJlZVByZWZpeCwgdHJlZVN1ZmZpeDsKdmVjdG9yPGludD4gdmFsOwoKaW50IGdldElEKGludCB4KQp7CiAgICByZXR1cm4gbG93ZXJfYm91bmQodmFsLmJlZ2luKCksIHZhbC5lbmQoKSwgeCkgLSB2YWwuYmVnaW4oKSArIDE7Cn0Kdm9pZCBkbmMoaW50IGwsIGludCByLCBpbnQgb3B0bCwgaW50IG9wdHIpCnsKICAgIGlmIChyIDwgbCkKICAgICAgICByZXR1cm4gOwogICAgaW50IG0gPSBsICsgciA+PiAxOwogICAgaWkgYmVzdCA9IGlpKElORiwgSU5GKTsKICAgIGZvciAoaW50IGkgPSBvcHRsOyBpIDw9IG9wdHI7IGkrKykKICAgIHsKICAgICAgICB0cmVlU3VmZml4LnVwZGF0ZShhW2ldLCAtMSk7CiAgICAgICAgdHJlZVByZWZpeC51cGRhdGUoYVtpXSwgMSk7CiAgICAgICAgYmVzdCA9IG1pbihiZXN0LCBpaSh0cmVlUHJlZml4LmdldFN1ZmZpeChiW21dICsgMSkgKyB0cmVlU3VmZml4LmdldFByZWZpeChiW21dIC0gMSksIGkpKTsKICAgIH0KICAgIGFucyArPSBiZXN0LmZpOwogICAgZm9yIChpbnQgaSA9IG9wdGw7IGkgPD0gb3B0cjsgaSsrKQogICAgewogICAgICAgIHRyZWVQcmVmaXgudXBkYXRlKGFbaV0sIC0xKTsKICAgICAgICB0cmVlU3VmZml4LnVwZGF0ZShhW2ldLCAxKTsKICAgIH0KICAgIGRuYyhsLCBtIC0gMSwgb3B0bCwgYmVzdC5zZSk7CiAgICBmb3IgKGludCBpID0gb3B0bDsgaSA8PSBiZXN0LnNlIC0gMTsgaSsrKQogICAgewogICAgICAgIHRyZWVQcmVmaXgudXBkYXRlKGFbaV0sIDEpOwogICAgICAgIHRyZWVTdWZmaXgudXBkYXRlKGFbaV0sIC0xKTsKICAgIH0KICAgIGRuYyhtICsgMSwgciwgYmVzdC5zZSwgb3B0cik7CiAgICBmb3IgKGludCBpID0gb3B0bDsgaSA8PSBiZXN0LnNlIC0gMTsgaSsrKQogICAgewogICAgICAgIHRyZWVQcmVmaXgudXBkYXRlKGFbaV0sIC0xKTsKICAgICAgICB0cmVlU3VmZml4LnVwZGF0ZShhW2ldLCAxKTsKICAgIH0KfQoKdm9pZCBzb2x2ZSgpCnsKICAgIGFucyA9IDA7CiAgICBjaW4gPj4gbiA+PiBtOwogICAgdmFsLmNsZWFyKCk7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBuOyBpKyspCiAgICB7CiAgICAgICAgY2luID4+IGFbaV07CiAgICAgICAgdmFsLnB1c2hfYmFjayhhW2ldKTsKICAgIH0KICAgIGZvciAoaW50IGkgPSAxOyBpIDw9IG07IGkrKykKICAgIHsKICAgICAgICBjaW4gPj4gYltpXTsKICAgICAgICB2YWwucHVzaF9iYWNrKGJbaV0pOwogICAgfQogICAgdmFsLnB1c2hfYmFjaygwKTsKICAgIHNvcnQodmFsLmJlZ2luKCksIHZhbC5lbmQoKSk7CiAgICB2YWwucmVzaXplKHVuaXF1ZSh2YWwuYmVnaW4oKSwgdmFsLmVuZCgpKSAtIHZhbC5iZWdpbigpKTsKICAgIHNvcnQoYiArIDEsIGIgKyBtICsgMSk7CiAgICBhWzBdID0gMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IG47IGkrKykKICAgICAgICBhW2ldID0gZ2V0SUQoYVtpXSk7CiAgICBmb3IgKGludCBpID0gMTsgaSA8PSBtOyBpKyspCiAgICAgICAgYltpXSA9IGdldElEKGJbaV0pOwogICAgdHJlZVByZWZpeCA9IHRyZWVTdWZmaXggPSBGZW53aWNrVHJlZSh2YWwuc2l6ZSgpKTsKICAgIGZvciAoaW50IGkgPSAwOyBpIDw9IG47IGkrKykKICAgIHsKICAgICAgICBhbnMgKz0gdHJlZVN1ZmZpeC5nZXRTdWZmaXgoYVtpXSArIDEpOwogICAgICAgIHRyZWVTdWZmaXgudXBkYXRlKGFbaV0sIDEpOwogICAgfQogICAgZG5jKDEsIG0sIDAsIG4pOwogICAgY291dCA8PCBhbnMsIGVsOwp9CgppbnQgbWFpbigpCnsKICAgIGlvc19iYXNlOjpzeW5jX3dpdGhfc3RkaW8oMCk7IGNpbi50aWUoMCk7IGNvdXQudGllKDApOwogICAgaWYgKGZvcGVuKEZJTEVOQU1FIi5JTlAiLCAiciIpKQogICAgewogICAgICAgIGZyZW9wZW4oRklMRU5BTUUiLklOUCIsICJyIiwgc3RkaW4pOwogICAgICAgIGlmIChpc19icnV0ZSkKICAgICAgICAgICAgZnJlb3BlbihGSUxFTkFNRSJfVFJBVS5PVVQiLCAidyIsIHN0ZG91dCk7CiAgICAgICAgZWxzZQogICAgICAgICAgICBmcmVvcGVuKEZJTEVOQU1FIi5PVVQiLCAidyIsIHN0ZG91dCk7CiAgICB9CgogICAgaW50IG50ZXN0OwogICAgaWYgKG11bHRpX3Rlc3QpCiAgICAgICAgY2luID4+IG50ZXN0OwogICAgZWxzZQogICAgICAgIG50ZXN0ID0gMTsKICAgIGZvciAoaW50IGl0ZXN0ID0gMTsgaXRlc3QgPD0gbnRlc3Q7IGl0ZXN0KyspCiAgICB7CiAgICAgICAgLy8gY291dCA8PCBpdGVzdCwgZWw7CiAgICAgICAgc29sdmUoKTsKICAgIH0KfQ==

Success #stdin #stdout 0.01s 5800KB

stdin

copy

Standard input is empty

stdout

copy

https://ideone.com/1m54Oq

language:

C++14 (gcc 8.3)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language