Submission #42357

#	Time	Username	Problem	Language	Result	Execution time	Memory
42357		dqhungdl	즐거운 채소 기르기 (JOI14_growing)	C++14	30 / 100	39 ms	2156 KiB

growing

#include <bits/stdc++.h>
using namespace std;

typedef pair<int64_t,int64_t> ii;
int64_t n,res=0,treeL[300005],treeR[300005];
ii a[300005];

void UpdateL(int64_t idx)
{
    while(idx>0)
    {
        treeL[idx]++;
        idx-=idx&-idx;
    }
}

int64_t QueryL(int64_t idx)
{
    int64_t rs=0;
    while(idx<=n)
    {
        rs+=treeL[idx];
        idx+=idx&-idx;
    }
    return rs;
}

void UpdateR(int64_t idx)
{
    while(idx<=n)
    {
        treeR[idx]++;
        idx+=idx&-idx;
    }
}

int64_t QueryR(int64_t idx)
{
    int64_t rs=0;
    while(idx>0)
    {
        rs+=treeR[idx];
        idx-=idx&-idx;
    }
    return rs;
}

int main()
{
    ios_base::sync_with_stdio(false);
    //freopen("TEST.INP","r",stdin);
    cin>>n;
    for(int64_t i=1; i<=n; i++)
    {
        cin>>a[i].first;
        a[i].second=i;
    }
    sort(a+1,a+n+1);
    int64_t tmp=1,L=0,R=n+1;
    for(int64_t i=2; i<=n; i++)
        if(a[i].first!=a[i-1].first)
        {
            int id=-1;
            for(int j=tmp; j<i; j++)
            {
                int64_t pos=a[j].second+QueryL(a[j].second)-QueryR(a[j].second);
                int64_t moveL=pos-L-1;
                int64_t moveR=R-pos-1;
                if(moveL<moveR)
                {
                    res+=moveL;
                    L++;
                    UpdateL(a[j].second);
                }
                else
                {
                    id=j;
                    break;
                }
            }
            if(id!=-1)
                for(int j=i-1; j>=id; j--)
                {
                    int64_t pos=a[j].second+QueryL(a[j].second)-QueryR(a[j].second);
                    int64_t moveR=R-pos-1;
                    res+=moveR;
                    R--;
                    UpdateR(a[j].second);
                }
            tmp=i;
        }
    cout<<res;
}

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