Submission #303574

#	Time	Username	Problem	Language	Result	Execution time	Memory
303574		vipghn2003	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	86 ms	25976 KiB

shoes

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

const int N=1e5+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;
}
/*
int main()
{
    int n;
    cin>>n;
    vector<int>a(n);
    for(auto&x:a) cin>>x;
    cout<<count_swaps(a);
}
/*
4
2 1 -1 -2
*/

Compilation message (stderr)

shoes.cpp:68:1: warning: "/*" within comment [-Wcomment]
   68 | /*
      |

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