제출 #924613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
924613		LucaLucaM	Arranging Shoes (IOI19_shoes)	C++17	10 / 100	1 ms	600 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <map>

typedef long long ll;

struct segtreeLazy {
  struct Node {
    int maxi, lazy;
    Node() {}

    Node operator + (const Node &other) {
      Node ret;
      ret.maxi = std::max(maxi, other.maxi);
      ret.lazy = 0;
      return ret;
    }
  };

  int N;
  std::vector<Node> aint;

  segtreeLazy() {}
  segtreeLazy(int _n) {
    N = _n;
    int n = 1;
    while (n < _n) {
      n <<= 1;
    }
    n <<= 1;
    n |= 1;
    aint.resize(n);
    for (int i = 0; i < n; i++) {
      aint[i].maxi = 0;
      aint[i].lazy = 0;
    }
  }

  void push(int node, int tl, int tr) {
    if (aint[node].lazy == 0) {
      return;
    }
    aint[node].maxi += aint[node].lazy;
    if (tl < tr) {
      aint[2 * node].lazy += aint[node].lazy;
      aint[2 * node + 1].lazy += aint[node].lazy;
    }
    aint[node].lazy = 0;
  }

  void upd(int node, int tl, int tr, int l, int r, int add) {
    push(node, tl, tr);
    if (l <= tl && tr <= r) {
      aint[node].lazy += add;
    } else {
      int mid = (tl + tr) / 2;
      if (l <= mid) {
        upd(2 * node, tl, mid, l, r, add);
      }
      if (mid < r) {
        upd(2 * node + 1, mid + 1, tr, l, r, add);
      }
      push(2 * node, tl, mid);
      push(2 * node + 1, mid + 1, tr);
      aint[node] = aint[2 * node] + aint[2 * node + 1];
    }
  }

  int que(int node, int tl, int tr, int l, int r) {
    push(node, tl, tr);
    if (l <= tl && tr <= r) {
      return aint[node].maxi;
    }
    int mid = (tl + tr) / 2;
    int ret = -1;
    if (l <= mid) {
      ret = std::max(ret, que(2 * node, tl, mid, l, r));
    }
    if (mid < r) {
      ret = std::max(ret, que(2 * node + 1, mid + 1, tr, l, r));
    }
    return ret;
  }
  void update(int l, int r, int add) {
    upd(1, 1, N, l, r, +add);
  }
  int query(int l, int r) {
    return que(1, 1, N, l, r);
  }
};

ll count_swaps(std::vector<int> s) {
  ll answer = 0;
  std::map<int, int> pos;
  int n = (int) s.size();
  int nxt[n] = {};
  for (int i = n - 1; i >= 0; i--) {
    pos[s[i]] = i;
    nxt[i] = pos[-s[i]];
  }
  segtreeLazy aint(n);
  for (int i = 1; i <= n; i++) {
    aint.update(i, i, i);
  }
  bool block[n] = {};
  int realPos[n] = {};
  for (int i = 0; i < n; i++) {
    realPos[i] = i;
  }
  for (int i = 0; i < n; i++) {
    if (block[i]) {
      continue;
    }
    int j = nxt[i];
    block[j] = true;
    if (s[i] < 0) {
      answer += realPos[j] - realPos[i] - 1;
    } else {
      answer += realPos[j] - realPos[i];
    }
    for (int k = i; k <= j; k++) {
      realPos[k]++;
    }

//    block[j] = true;
////    std::cout << "! " << i << ' ' << j << '\n';
//    aint.update(i + 1, j + 1, +1);
//    if (s[i] < 0) {
//      answer += aint.query(j + 1, j + 1) - aint.query(i + 1, i + 1) - 1;
//    } else {
//      answer += aint.query(j + 1, j + 1) - aint.query(i + 1, i + 1);
//    }
  }
  return answer;
}

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