제출 #1307772

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307772		lufychop	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	384 ms	153844 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

long long n;
map<long long,deque<long long>> mp;
vector<long long> seg(1000000,0);

void update_tree(int pos,int val,int l,int r,int pos_tree)
{
    if(pos<l || r<pos || l>r)
    {
        return;
    }
    if(pos==l && pos==r)
    {
        seg[pos_tree]=val;
        return;
    }
    update_tree(pos,val,l,(l+r)/2,pos_tree*2);
    update_tree(pos,val,(l+r)/2+1,r,pos_tree*2+1);
    seg[pos_tree]=seg[pos_tree*2]+seg[pos_tree*2+1];
}
int sum_tree(int ql,int qr,int l,int r,int pos_tree)
{
    if(r<ql || qr<l)
    {
        return 0;
    }
    if(ql<=l && r<=qr)
    {
        return seg[pos_tree];
    }
    return sum_tree(ql,qr,l,(l+r)/2,pos_tree*2)+sum_tree(ql,qr,(l+r)/2+1,r,pos_tree*2+1);
}

long long count_swaps(vector<int> s)
{
    n=s.size();
    long long ans=0;
    long long LL=0,RR=n-1;
    for(int i=0;i<n;i++)
    {
        mp[s[i]].push_back(i);
    }
    while(LL<RR)
    {
        if(s[LL]!=0)
        {
            long long tmp=0;
            long long L=LL+1;
            long long R=mp[-s[LL]].front();
            mp[s[LL]].pop_front();
            mp[-s[LL]].pop_front();
            for(int i=L;i<=R;i++)
            {
                if(s[i]==0)
                {
                    tmp++;
                }
            }
            // cout<<tmp<<" ";
            tmp=sum_tree(L,R,0,n-1,1);
            ans=ans+R-L-tmp;
            // cout<<tmp<<"\n";
            if(s[R]<0)
            {
                ans++;
            }
            s[R]=0;
            s[LL]=0;
            update_tree(R,1,0,n-1,1);
            update_tree(LL,1,0,n-1,1);
        }
        if(s[RR]!=0)
        {
            long long tmp=0;
            long long L=mp[-s[RR]].back();
            long long R=RR-1;
            mp[-s[RR]].pop_back();
            mp[s[RR]].pop_back();
            for(int i=L;i<=R;i++)
            {
                if(s[i]==0)
                {
                    tmp++;
                }
            }
            // cout<<tmp<<" ";
            tmp=sum_tree(L,R,0,n-1,1);
            ans=ans+R-L-tmp;
            // cout<<tmp<<"\n";
            if(s[L]>0)
            {
                ans++;
            }
            s[L]=0;
            s[RR]=0;
            update_tree(L,1,0,n-1,1);
            update_tree(RR,1,0,n-1,1);
        }
        // cout<<LL<<RR;
        LL++;
        RR--;
    }
	return ans;
}

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