Submission #383620

#	Time	Username	Problem	Language	Result	Execution time	Memory
383620		sad	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	78 ms	31852 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
const int N=100090;
int tree[4*N];
vector<int>v[N][3];
int get (int ind,int st,int end,int l,int r)
{
    if(l>end||r<st)return 0;
    if(l<=st&&end<=r)return tree[ind];
    int m=(st+end)/2;
    return (get(ind*2+1,st,m,l,r)+get(ind*2+2,m+1,end,l,r));
}
void up(int ind,int st,int end,int uind,int x)
{
    if(uind>end||uind<st)return;
    if(st==end)
    {
        tree[ind]+=x;return;
    }
    int m=(st+end)/2;
    up(ind*2+1,st,m,uind,x);
    up(ind*2+2,m+1,end,uind,x);
    tree[ind]=tree[ind*2+1]+tree[ind*2+2];
}int n;
long long count_swaps(std::vector<int> s) {

    n=s.size();ll re=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]<0)v[-s[i]][0].pb(i);
        else v[s[i]][1].pb(i);
    }
    for(int i=0;i<=n;i++)
    {
        reverse(v[i][1].begin(),v[i][1].end());
        reverse(v[i][0].begin(),v[i][0].end());
    }
    for(int i=0;i<n;i++)
    {
        if(s[i]<0)
        {
            if(v[-s[i]][0].size()==0)continue;
            if(v[-s[i]][0].back()!=i)continue;
            int x=v[-s[i]][1].back();
            re+=x-i-1;
            re+=get(0,0,n-1,i+1,x);
            up(0,0,n-1,x,-1);
            v[-s[i]][1].pop_back();
            v[-s[i]][0].pop_back();
        }
          else {  if(v[s[i]][1].size()==0)continue;
            if(v[s[i]][1].back()!=i)continue;
            int x=v[s[i]][0].back();
            re+=x-i;
            re+=get(0,0,n-1,i+1,x);
            up(0,0,n-1,x,-1);
            v[s[i]][0].pop_back();
            v[s[i]][1].pop_back();
            }
            //cout<<i<<" "<<re<<endl;
    }
    return re;
}

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