Submission #292461

#	Time	Username	Problem	Language	Result	Execution time	Memory
292461		Autoratch	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	191 ms	139128 KiB

shoes

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

const int N = 2e5 + 1;
const int H = 1e5;

int n,fw[N];
queue<int> res[N];
long long ans;

void update(int idx,int val){ while(idx<N) fw[idx]+=val,idx+=(idx & -idx); }

int read(int idx){ int val = 0; while(idx>0) val+=fw[idx],idx-=(idx & -idx); return val; }

long long count_swaps(vector<int> s) 
{
    n = s.size();
    for(int i = 1;i <= n;i++) update(i,1);
    for(int i = 1;i <= n;i++)
    {
        int x = s[i-1];
        if(!res[-x+H].empty())
        {
            int j = res[-x+H].front();
            res[-x+H].pop();
            ans+=read(i-1)-read(j);
            if(x<0) ans++;
            update(i,-1);
            update(j,1);
        }
        else res[x+H].push(i);
    }
    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