Submission #304933

#	Time	Username	Problem	Language	Result	Execution time	Memory
304933		azberjibiou	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	266 ms	142356 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mxN=101010;
queue <int> que[2*mxN];
bool Chk[2*mxN];
int seg[8*mxN];
void init(int idx, int s, int e)
{
    seg[idx]=e-s+1;
    if(s!=e)
    {
        int mid=(s+e)/2;
        init(2*idx, s, mid);
        init(2*idx+1, mid+1, e);
    }
}
int sum(int idx, int s, int e, int str, int fin)
{
    if(s>fin || str>e)  return 0;
    if(str<=s && e<=fin)    return seg[idx];
    int mid=(s+e)/2;
    return sum(2*idx, s, mid, str, fin)+sum(2*idx+1, mid+1, e, str, fin);
}
void upd(int idx, int s, int e, int pos)
{
    if(pos<s || pos>e)  return;
    seg[idx]--;
    if(s!=e)
    {
        int mid=(s+e)/2;
        upd(2*idx, s, mid, pos);
        upd(2*idx+1, mid+1, e, pos);
    }
}
long long count_swaps(vector<int> s)
{
    ll ans=0;
	int N=s.size()/2;
	for(int i=0;i<2*N;i++)
    {
        que[s[i]+N].push(i);
    }
    init(1, 0, 2*N-1);
	for(int i=0;i<2*N;i++)
    {
        if(Chk[i])  continue;
        int left=N+s[i];
        int right=N-s[i];
        int nxt=que[right].front();
        que[right].pop();
        que[left].pop();
        ans+=sum(1, 0, 2*N-1, i, nxt)-2;
        if(s[i]>0)  ans++;
        upd(1, 0, 2*N-1, nxt);
        upd(1, 0, 2*N-1, i);
        Chk[i]=true;
        Chk[nxt]=true;
    }
    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