Submission #1164085

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164085		s3yoonpark	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	158 ms	158364 KiB

shoes

#include <bits/stdc++.h> 
#define ssize(x) (int)x.size() 
using namespace std; 
const int N = 1E5 + 5; 
int n;
map<int,queue<int>> st;  
bool processed[N]; 
struct Node {
  Node *l, *r; 
  long long val; 
  Node (long long v) { val = v, l = nullptr, r = nullptr; }
  Node (Node *ll, Node *rr) { 
    l = ll, r = rr; 
    val = 0; 
    if (l != nullptr) val = val + l->val; 
    if (r != nullptr) val = val + r->val; 
  }
  Node (Node *cp) { val = cp->val, l = cp->l, r = cp->r; }
}; 
void build (Node* t, int l = 1, int r = n) {
  if (l == r) {
    t->val = 1ll; 
    return; 
  }
  t->l = new Node(0ll), t->r = new Node(0ll); 
  int mid = (l + r) / 2; 
  build(t->l, l, mid); 
  build(t->r, mid + 1, r); 
  t->val = t->l->val + t->r->val; 
}
void update(Node* t, int ql, int val, int l = 1, int r = n) {
  if (ql < l || ql > r) return; 
  if (l == r && l == ql) {
    t->val = val; 
    return; 
  }
  int mid = (l + r) / 2; 
  update(t->l, ql, val, l, mid); 
  update(t->r, ql, val, mid + 1, r); 
  t->val = t->l->val + t->r->val; 
}
long long query(Node *t, int a, int b, int l = 1, int r = n) {
  if (b < l || a > r) return 0ll; 
  if (l >= a && r <= b) return t->val; 
  int mid = (l + r) / 2; 
  return query(t->l, a, b, l, mid) + query(t->r, a, b, mid + 1, r); 
}
Node *segtree = new Node(0ll); 
long long count_swaps(vector<int> S) {
  n = ssize(S);  
  for (int i = 1; i <= n; i++) {
    int e = S[i - 1]; 
    st[e].push(i);
  }
  build(segtree); 
  int ans = 0; 
  for (int i = 1; i <= n; i++) {
    int e = S[i - 1], ce = -S[i - 1];
    if (processed[i]) continue; 
    int id = st[e].front(), idc = st[ce].front(); 
    st[e].pop(), st[ce].pop();  
    processed[id] = true, processed[idc] = true; 
    int rid = query(segtree, 1, id), ridc = query(segtree, 1, idc);
    if (e > 0) {
      ans += ridc - rid;
    } else {
      ans += ridc - rid - 1; 
    }
    update(segtree, id, 0ll);
    update(segtree, idc, 0ll); 
  }
  return ans; 
}

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