Submission #1036720

#	Time	Username	Problem	Language	Result	Execution time	Memory
1036720		cjoa	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	604 KiB

shoes

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

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 increment(int p, int id, int L, int R) {
      if (p < L or p > R)
         return;
      if (L == R) {
         tree[id]++;
         return;
      }
      int mid = (L + R) / 2;
      increment(p, 2*id, L, mid);
      increment(p, 2*id+1, mid+1, R);
      tree[id] = tree[2*id] + tree[2*id+1];
   }
   void increment(int p) {
      increment(p, 1, 0, N-1);
   }
};

long long count_swaps(std::vector<int> s) {
   vector< pair<int,int> > parejas;
   map<int,int> last;
   for (int i = int(s.size())-1; i >= 0; --i) {
      int x = s[i];
      if (last.count(-x)) {
         parejas.emplace_back(i, last[-x]);
         last.erase(-x);
      }
      else
         last[x] = 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.increment(r);
   }

	return ret;
}

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