Submission #1046603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1046603		sofijavelkovska	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	57 ms	15956 KiB

shoes

#include "shoes.h"
//#include "grader.cpp"

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

const int MAXN=(1<<18);

int tree[2*MAXN-1]={0};

int find(int x, int l, int r, int lt, int rt)
{
    if (l>=rt || r<=lt)
        return 0;
    if (l>=lt && r<=rt)
        return tree[x];

    return find(2*x+1, l, (l+r)/2, lt, rt)+find(2*x+2, (l+r)/2, r, lt, rt);
}

void update(int x, int l, int r, int index, int value)
{
    if (l>index || r<=index)
        return;
    tree[x]=tree[x]+value;
    if (r-l==1)
        return;
    update(2*x+1, l, (l+r)/2, index, value);
    update(2*x+2, (l+r)/2, r, index, value);

    return;
}

long long count_swaps(vector<int> a) {

	int n=a.size()/2;
	vector<int> left[n+1], right[n+1];
	for (int i=0; i<2*n; i++)
    {
        if (a[i]<0)
            left[-a[i]].push_back(i);
        else
            right[a[i]].push_back(i);
    }
    int match[2*n];
    long long total=0;
    for (int i=1; i<=n; i++)
        for (int j=0; j<left[i].size(); j++)
        {
            match[min(left[i][j], right[i][j])]=max(left[i][j], right[i][j]);
            match[max(left[i][j], right[i][j])]=-1;
            if (right[i][j]<left[i][j])
                total=total+1;
        }
    for (int i=0; i<2*n; i++)
    {
        if (match[i]==-1)
            continue;
        total=total+match[i]-i-1;
        total=total-find(0, 0, MAXN, i, match[i]);
        update(0, 0, MAXN, match[i], 1);
    }

	return total;
}

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:48:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |         for (int j=0; j<left[i].size(); j++)
      |                       ~^~~~~~~~~~~~~~~

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