Submission #1037344

#	Time	Username	Problem	Language	Result	Execution time	Memory
1037344		biserailieva	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	335 ms	151340 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
 
struct SegmentTree
{
   int N;
   vector<int> tree;
   SegmentTree(int _N) : N(_N), tree(4*_N){
   }
   int query(int p, int q, int id, int L, int R)
   {
      if (L > q or R < p)
         return 0;
      if (p <= L and R <= q)
         return tree[id];
      int mid = (L + R) / 2;
      return query(p, q, 2*id, L, mid) + query(p, q, 2*id+1, mid+1, R);
   }
   int query(int p, int q)
   {
      return query(p, q, 1, 0, N-1);
   }
   void increase(int p, int val, int id, int L, int R)
   {
      if (p < L or p > R)
         return;
      if (L == R) {
         tree[id] += val;
         return;
      }
      int mid = (L + R) / 2;
      increase(p, val, 2*id, L, mid);
      increase(p, val, 2*id+1, mid+1, R);
      tree[id] = tree[2*id] + tree[2*id+1];
   }
   void increase(int p, int val)
   {
      increase(p, val, 1, 0, N-1);
   }
};
 
long long count_swaps(std::vector<int> s)
{
   vector< pair<int,int> > parejas;
   map<int,queue<int> > last;
   for (int i = int(s.size())-1; i >= 0; --i)
   {
      int x = s[i];
      if (!last[-x].empty())
      {
         parejas.emplace_back(i, last[-x].front());
         last[-x].pop();
      }
      else
         last[x].push(i);
   }
   reverse(parejas.begin(), parejas.end());
   long long ret = 0;
   SegmentTree st(s.size());
   for (auto p : parejas)
   {
      int l, r;
      tie(l, r) = p;
      int steps = r - l - 1 - st.query(l+1, r-1);
      if (s[l] > 0) {
         ++steps;
      }
      ret += steps;
      st.increase(r, 1);
   }
    return ret;
}

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