제출 #1283282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1283282		cris71	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	137 ms	139784 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
int const lmax=2e5+7;
vector<int> w;
queue <int> qplus[lmax/2],qminus[lmax/2];
long long int aib[lmax];
int n,v[lmax];
int query(int pos)
{
    pos++;
    long long int sum=0;
    for(int i=pos;i>0;i-=(i&-i))
    {
        sum+=aib[i];
    }
    return sum;
}
void update(int pos,long long int val)
{
    pos++;
    for(int i=pos;i<=n;i+=(i&-i))
    {
        aib[i]+=val;
    }
}
void debug()
{
    for(int i=0;i<n;i++)cout<<v[i]<<" ";
    cout<<"\n";
}
long long int count_swaps(vector<int> vv)
{
    long long int ans=0;
    n=vv.size();
    for(int i=0;i<n;i++)v[i]=vv[i];
    for(int i=0;i<n;i++)update(i,1);
    //debug();
    for(int i=0;i<n;i++)
    {
        if(v[i]>0)qplus[v[i]].push(i);
        else qminus[-v[i]].push(i);
    }
    ///the mappings
    int lastb=-1;
    for(int i=0;i<n;i++)
    {
        if((query(i)-query(i-1))==0 or qplus[abs(v[i])].empty()==true or lastb==i)continue;
        int a,b;
        if(v[i]>0)
        {
            a=qplus[v[i]].front();///i
            b=qminus[v[i]].front();
            qplus[v[i]].pop();
            qminus[v[i]].pop();
        }
        else
        {
            a=qminus[-v[i]].front();///i
            b=qplus[-v[i]].front();
            qplus[-v[i]].pop();
            qminus[-v[i]].pop();
        }
        //cout<<a<<" "<<b<<"\n";
        ///i in vector -> i+1 in aib
        ///a=i, b=i+h, b>a
        ans+=(query(b-1)-query(a));
        if(v[i]>0)ans++;
        update(b,-1);
        update(a,-1);///does not help at least i dont think
        lastb=b;
    }


    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