Submission #1247445

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247445		tvgk	즐거운 채소 기르기 (JOI14_growing)	C++20	100 / 100	184 ms	11648 KiB

growing

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<ll, ll>
const long mxN = 3e5 + 7;

int a[mxN], tree[mxN * 4], n;
ll pre[mxN], suf[mxN];
vector<int> val;

int Get(int u, int j = 1, int l = 0, int r = val.size() - 1)
{
    if (r <= u)
        return 0;

    if (u < l)
        return tree[j];

    int mid = (l + r) / 2;
    return Get(u, j * 2, l, mid) + Get(u, j * 2 + 1, mid + 1, r);
}

void Upd(int vt, int j = 1, int l = 0, int r = val.size() - 1)
{
    if (l > vt || vt > r)
        return;

    tree[j]++;
    if (l == r)
        return;

    int mid = (l + r) / 2;
    Upd(vt, j * 2, l, mid);
    Upd(vt, j * 2 + 1, mid + 1, r);
}

void Reset(int j = 1, int l = 0, int r = val.size() - 1)
{
    tree[j] = 0;
    if (l == r)
        return;

    int mid = (l + r) / 2;
    Reset(j * 2, l, mid);
    Reset(j * 2 + 1, mid + 1, r);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        val.push_back(a[i]);
    }
    sort(val.begin(), val.end());
    val.erase(unique(val.begin(), val.end()), val.end());

    for (int i = 1; i <= n; i++)
    {
        int tmp = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
        pre[i] = Get(tmp);
        Upd(tmp);
    }
    Reset();

    for (int i = n; i >= 1; i--)
    {
        int tmp = lower_bound(val.begin(), val.end(), a[i]) - val.begin();
        suf[i] = Get(tmp);
        Upd(tmp);
    }

    ll ans = 0;
    for (int i = 1; i <= n; i++)
        ans += min(pre[i], suf[i]);
    cout << ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 15 / 15
• Subtask 4: 55 / 55