Submission #1105929

#	Time	Username	Problem	Language	Result	Execution time	Memory
1105929		vjudge1	Untitled (POI11_rot)	C++17	100 / 100	166 ms	22600 KiB

Main

#include <bits/stdc++.h>
#define ll long long
const ll mod=1e9+7;
#define fi first
#define se second
using namespace std;
int st[4000005],en[4000005],n,N=1,a[200005],nn,u,l[4000005],r[4000005];
int bit[200005];
void update(int u,int v)
{
    int idx=u;
    while (idx<=n)
    {
        bit[idx]+=v;
        idx+=(idx&(-idx));
    }
}
int getSum(int u)
{
    if (u==0) return 0;
    int idx=u,tong=0;
    while (idx>0)
    {
        tong+=bit[idx];
        idx-=(idx&(-idx));
    }
    return tong;
}
int get(int l,int r)
{
    return getSum(r)-getSum(l-1);
}
void solve()
{
    int hao=N;
    cin>>u;
    if (u!=0)
    {
        nn++;
        a[nn]=u;
        st[hao]=nn;
        en[hao]=nn;
    }
    else
    {
        int le=N+1;
        N++;
        solve();
        int ri=N+1;
        N++;
        solve();
        st[hao]=st[le];
        en[hao]=en[ri];
        l[hao]=le;
        r[hao]=ri;
    }
}
ll dfs(int u)
{
    ll ketqua=0,maxx1=0,maxx2=0;
    if (st[u]==en[u])
    {
        update(a[st[u]],1);
        return 0;
    }
    int le=l[u];
    int ri=r[u];
    if (en[ri]-st[ri]<en[le]-st[le]) swap(le,ri);
    ketqua+=dfs(le);
    for (int i=st[le];i<=en[le];++i)
    {
        update(a[i],-1);
    }
    ketqua+=dfs(ri);
    for (int i=st[le];i<=en[le];++i)
    {
        maxx1+=getSum(a[i]-1);
        maxx2+=get(a[i]+1,n);
    }
    for (int i=st[le];i<=en[le];++i)
    {
        update(a[i],1);
    }
    return ketqua+min(maxx1,maxx2);
}
signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    solve();
    cout<<dfs(1);
    
}

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 9 / 9
• Subtask 7: 9 / 9
• Subtask 8: 9 / 9
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 10 / 10