Submission #339035

#	Time	Username	Problem	Language	Result	Execution time	Memory
339035		markussie	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	166 ms	23020 KiB

shoes

#include "shoes.h"
#include <vector>
#include <algorithm>

#pragma GCC optimize("O2")

using namespace std;

vector<int> t;

void update(int v, int tl, int tr, int pos)
{
  if(tl == tr)
    ++t[v];
  else
    {
      int mid = (tl + tr)/2;
      if(pos <= mid)
	update(v*2, tl, mid, pos);
      else
	update(v*2+1, mid+1, tr, pos);
      t[v] = t[v*2] + t[v*2+1];
    }
}

int query(int v, int tl, int tr, int l, int r)
{
  if(l > r)
    return 0;
  if(tl == l && tr == r)
    return t[v];
  int mid = (tl + tr) / 2;
  return query(v*2, tl, mid, l, min(mid, r)) +
    query(v*2+1, mid+1, tr, max(mid+1, l), r);
}

long long count_swaps(std::vector<int> s)
{
  int n = s.size();
  t.resize(4*n);
  vector<vector<int>> l(n), r(n);

  for(int i = 0; i < n; ++i)
    if(s[i] < 0)
      l[-s[i]-1].push_back(i);
    else
      r[s[i]-1].push_back(i);

  long long ans = 0;
  vector<char> used(n);
  vector<int> cnt(n);
  for(int i = 0; i < n; ++i)
    {
      if(used[i])
	continue;
      if(s[i] < 0)
	{
	  ans += r[-s[i]-1][cnt[-s[i]-1]] - i - query(1, 0, n-1, i, r[-s[i]-1][cnt[-s[i]-1]]) - 1;
	  used[r[-s[i]-1][cnt[-s[i]-1]]] = 1;
	  update(1, 0, n-1, r[-s[i]-1][cnt[-s[i]-1]]);
	}
      else
	{
	  ans += l[s[i]-1][cnt[s[i]-1]] - i - query(1, 0, n-1, i, l[s[i]-1][cnt[s[i]-1]]);
	  used[l[s[i]-1][cnt[s[i]-1]]] = 1;
	  update(1, 0, n-1, l[s[i]-1][cnt[s[i]-1]]);
	}
      ++cnt[abs(s[i])-1];
    }
  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