Submission #1247440

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247440		tvgk	즐거운 채소 기르기 (JOI14_growing)	C++20	30 / 100	16 ms	1988 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 v, int j = 1, int l = 0, int r = val.size() - 1)
{
    if (u > r || l > v)
        return 0;

    if (u <= l && r <= v)
        return tree[j];

    int mid = (l + r) / 2;
    return Get(u, v, j * 2, l, mid) + Get(u, v, 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] = pre[i - 1] + Get(tmp + 1, val.size() - 1);
        Upd(tmp);
    }
    Reset();

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

        ans = min(ans, suf[i] + pre[i - 1]);
    }
    cout << ans;
}

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