Submission #380021

#	Time	Username	Problem	Language	Result	Execution time	Memory
380021		madlogic	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	755 ms	151916 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"

using namespace std;

struct SegmentTree {
  int n;
  vector<int> a, st;
  SegmentTree(vector<int> b) {
    n = (int) b.size();
    a = b;
    st.resize(4 * n);
    build(0, n - 1, 1);
  }

  inline int L(int n) {
    return (n << 1);
  }

  int build(int l, int r, int node) {
    if (l == r) {
      st[node] = a[l];
      return st[node];
    }
    int mid = l + r >> 1;
    int left = build(l, mid, L(node));
    int right = build(mid + 1, r, L(node) + 1);
    return st[node] = st[(node << 1)] + st[(node << 1) + 1];
  }

  int query(int l, int r) {
    return rsq(0, n - 1, l, r, 1);
  }

  void update(int ind, int k) {
    upd(0, n - 1, ind, k, 1);
  }

  int upd(int l, int r, int ind, int val, int node) {
    if (l == r) {
      st[node] += val;
      return st[node];
    }
    int mid = l + r >> 1;
    if (ind <= mid)
      upd(l, mid, ind, val, (node << 1));
    else
      upd(mid + 1, r, ind, val, (node << 1) + 1);
    return st[node] = st[(node << 1)] + st[(node << 1) + 1];
  }

  int rsq(int l, int r, int lb, int rb, int node) {
    if (l > rb || r < lb)
      return 0;
    if (l >= lb && r <= rb)
      return st[node];
    int mid = l + r >> 1;
    int left = rsq(l, mid, lb, rb, L(node));
    int right = rsq(mid + 1, r, lb, rb, L(node) + 1);
    return left + right;
  }
};

long long count_swaps(std::vector<int> s) {
  int n = (int) s.size();
  map<int, queue<int>> mp;
  for (int i = 0; i < n; i++) {
    mp[s[i]].push(i);
  }
  SegmentTree st(vector<int>(n, 0));
  long long res = 0;
  vector<bool> vis(n);
  for (int i = 0; i < n; i++) {
    if (vis[i]) {
      continue;
    }
    int pos = mp[-s[i]].front();
    vis[pos] = true;
    mp[-s[i]].pop();
    mp[s[i]].pop();
    int to;
    if (s[i] < 0) {
      to = i + 1;
    } else {
      to = i;
    }
    res += pos - to - st.query(to, pos);
    st.update(pos, 1);
  }
  return res;
}

Compilation message (stderr)

shoes.cpp: In member function 'int SegmentTree::build(int, int, int)':
shoes.cpp:25:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |     int mid = l + r >> 1;
      |               ~~^~~
shoes.cpp:26:9: warning: unused variable 'left' [-Wunused-variable]
   26 |     int left = build(l, mid, L(node));
      |         ^~~~
shoes.cpp:27:9: warning: unused variable 'right' [-Wunused-variable]
   27 |     int right = build(mid + 1, r, L(node) + 1);
      |         ^~~~~
shoes.cpp: In member function 'int SegmentTree::upd(int, int, int, int, int)':
shoes.cpp:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |     int mid = l + r >> 1;
      |               ~~^~~
shoes.cpp: In member function 'int SegmentTree::rsq(int, int, int, int, int)':
shoes.cpp:57:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   57 |     int mid = l + r >> 1;
      |               ~~^~~

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