Submission #893503

#	Time	Username	Problem	Language	Result	Execution time	Memory
893503		KaleemRazaSyed	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	49 ms	15196 KiB

shoes

#include<bits/stdc++.h>

using namespace std;

const int N = 1e5+5;
vector<int> v[N][2];
int ft[2 * N];

void update(int i)
{
  while(i < 2 * N)
    {
      ft[i]++;
      i += (i & -i);
    }
}
int sm(int i)
{
  int ans = 0;
  while(i > 0)
    {
      ans += ft[i];
      i -= (i & -i);
    }
  return ans;
}

long long count_swaps(vector<int> S)
{
  int tn = S.size(); // two  * n
  for(int i = tn - 1; i >= 0; i--)
    {
      if(S[i] > 0) v[S[i]][0].push_back(i);
      else v[-S[i]][1].push_back(i);
    }
  
  bool paired[tn];
  long long ans = 0;
  memset(paired, false, sizeof(paired));
  for(int i = 0; i < tn; i++)
    {
      if(paired[i]) continue;
      int val = -S[i], j;
      if(val > 0)
	{
	  while(paired[v[val][0].back()]) v[val][0].pop_back();
	  j = v[val][0].back();
	  v[val][0].pop_back();
	}
      else
	{
	  while(paired[v[-val][1].back()]) v[-val][1].pop_back();
	  j = v[-val][1].back();
	  v[-val][1].pop_back();
	}
      paired[i] = paired[j] = true;
      ans += j - i - 1;
      ans -= sm(j + 1) - sm(i + 1);
      update(i + 1);
      update(j + 1);
      if(S[i] > 0) ans++;
    }
  return ans;
}

/*int main()
{
  int n;
  cin >> n;
  vector<int> S(2 * n);
  for(int & i : S) cin >> i;
  cout << count_swaps(S) << endl;
  return 0;
}
*/

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