Submission #528939

#	Time	Username	Problem	Language	Result	Execution time	Memory
528939		megargayu	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	299 ms	33760 KiB

shoes

// https://oj.uz/problem/view/IOI19_shoes
#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define MAX_N 100000

// https://cp-algorithms.com/data_structures/segment_tree.html
vector<int> tree(4 * 2*MAX_N, 0);
int sum(int v, int tl, int tr, int l, int r)
{
  if (l > r) return 0;
  if (l == tl && r == tr) return tree[v];

  int tm = (tl + tr) / 2;
  return sum(v*2, tl, tm, l, min(r, tm))
         + sum(v*2+1, tm+1, tr, max(l, tm+1), r);
}

void update(int v, int tl, int tr, int pos, int new_val)
{
  if (tl == tr) tree[v] = new_val;
  else
  {
    int tm = (tl + tr) / 2;
    if (pos <= tm) update(v*2, tl, tm, pos, new_val);
    else           update(v*2+1, tm+1, tr, pos, new_val);

    tree[v] = tree[v*2] + tree[v*2+1];
  }
}

map<int, set<int>> ind;
vector<bool> ignored(MAX_N * 2, false);
ll count_swaps(vector<int> S)
{
  for (int i = 0; i < S.size(); ++i)
    ind[S[i]].insert(i);
  
  ll ans = 0;
  for (int i = 0; i < S.size(); ++i)
  {
    if (ignored[i]) continue;
    auto index = ind[-S[i]].lower_bound(i);
    ignored[*index] = true;

    ans += *index - i - sum(1, 0, S.size() - 1, i, *index); // TODO: extremely sus, probably wrong
    if (S[i] < 0) --ans;

    update(1, 0, S.size() - 1, *index, 1);

    ind[-S[i]].erase(index);
  }

  return ans;
}

Compilation message (stderr)

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

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