Submission #836223

#	Time	Username	Problem	Language	Result	Execution time	Memory
836223		Denkata	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	418 ms	680192 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"
//#include "grader.cpp"
using namespace std;
const int maxn = 1e5;
const int inf = 1e6+3;
long long i,j,ans,p,q,b[inf],n;
vector <int> v;
deque <int> pos[inf];
void upd(int p)
{
    while(p<=n)
    {
        b[p]++;
        p = (p|(p+1));
    }
}
long long rsq(int p)
{
    long long sum = 0;
    while(p>=0)
    {
        sum+=b[p];
        p = ((p&(p+1))-1);
    }
    return sum;
}
long long count_swaps(vector<int> s)
{
    ans = 0;
    j = 1;
    n = (int)s.size()*4+1;
    //memset(pos,-1,sizeof(pos));
    for(auto i:s)
    {
        if(!pos[-i+maxn].empty())
        {
            if(i>0)
                v.push_back(pos[-i+maxn].front()+1),pos[-i+maxn].pop_front();
            else v.push_back(pos[-i+maxn].front()-1),pos[-i+maxn].pop_front();
        }
        else
        {
            if(i>0)
                pos[i+maxn].push_back(j+1),v.push_back(j+1);
            else pos[i+maxn].push_back(j),v.push_back(j);
        }
        j+=2;
    }
    j = 0;
    for(auto i:v)
    {
       // cout<<i<<endl;
        ans+=j-rsq(i);
        upd(i);
        j++;
    }
    return ans;
}
/**
2
-2
-2
2
2

2
2
1
-1
-2
*/

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