제출 #303575

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
303575		vipghn2003	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	181 ms	21240 KiB

shoes

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

const int N=2e5+5;
int ST[4*N];
vector<int>posleft[N],posright[N];
bool vis[N];

void update(int id,int l,int r,int pos,int val)
{
    if(l>pos||r<pos) return ;
    if(l==r)
    {
        ST[id]+=val;
        return ;
    }
    int mid=(l+r)/2;
    update(id*2,l,mid,pos,val);
    update(id*2+1,mid+1,r,pos,val);
    ST[id]=ST[id*2]+ST[id*2+1];
}

int get(int id,int l,int r,int u,int v)
{
    if(u>r||v<l) return 0;
    if(u<=l&&r<=v) return ST[id];
    int mid=(l+r)/2;
    return get(id*2,l,mid,u,v)+get(id*2+1,mid+1,r,u,v);
}


long long count_swaps(vector<int>a)
{
    int n=a.size();
    for(int i=n-1;i>=0;i--)
    {
        if(a[i]<0) posleft[-a[i]].push_back(i);
        else posright[a[i]].push_back(i);
    }
    long long res=0;
    for(int i=0;i<n;i++)
    {
        if(vis[i]) continue;
        int cur=i,go;
        if(a[i]>0) go=posleft[a[i]].back();
        else go=posright[-a[i]].back();
        posleft[abs(a[i])].pop_back();
        posright[abs(a[i])].pop_back();
        vis[go]=true;
        res+=go+get(1,0,n-1,0,go)-(cur+get(1,0,n-1,0,cur))-1;
        if(a[i]>0) res++;
        //cout<<cur<<' '<<go<<' '<<get(1,0,n-1,0,go)<<'\n';
        update(1,0,n-1,0,1);
        if(go+1<n) update(1,0,n-1,go+1,-1);
    }
    return res;
}

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 15 / 15