Submission #144242

#	Time	Username	Problem	Language	Result	Execution time	Memory
144242		AlexLuchianov	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	485 ms	24716 KiB

shoes

#include <iostream>
#include <map>
#include <vector>

using namespace std;

#define ll long long
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

int const nmax = 200000;
int aib[1 + nmax];

void update(int x, int lim, int val){
  while(x <= lim){
    aib[x] += val;
    x += (x  ^ (x & (x - 1)));
  }
}

int query(int x){
  int result = 0;
  while(0 < x){
    result += aib[x];
    x = (x & (x - 1));
  }
  return result;
}

map<int,vector<int>> frec;

ll count_swaps(vector<int> v){
  int n = v.size();
  for(int i = 1;i <= n; i++)
    update(i, n, 1);

  for(int i = n; 1 <= i; i--)
    frec[v[i - 1]].push_back(i);

  ll result = 0;
  for(int i = 1;i <= n; i++){
    if(query(i) - query(i - 1) == 1){
      int val = v[i - 1], pos = frec[-val].back();

      frec[val].pop_back();
      frec[-val].pop_back();

      update(i, n, -1);
      update(pos, n, -1);
      if(val < 0)
        result += query(pos) - query(i);
      else
        result += query(pos) - query(i) + 1;
    }
  }
  return result;
}

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