Submission #953724

#	Time	Username	Problem	Language	Result	Execution time	Memory
953724		Trisanu_Das	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	198 ms	274352 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define int long long
 
int n, BIT[200005];
queue<int> l[200005], r[200005];
 
void upd(int val, int idx){
  for(int i = idx; i <= n; i += (i & -i)) BIT[i] += val;
}
 
int qry(int idx){
  int ans = 0;
  for(int i = idx; i > 0; i -= (i & -i)) ans += BIT[i];
  return ans;
}
 
int count_swaps(vector<signed> s){
  n = s.size();
  int ans = 0;
  for(int i = 1; i <= n; i++){
    int sz = s[i - 1];
    if(sz < 0){
      sz *= -1;
      if(r[sz].size()){
        int need = r[sz].front(); r[sz].pop();
        ans += qry(i) - qry(need - 1);
        upd(1, need);
      }else {
        l[sz].push(i);
        upd(1, i);
      }
    }else{
      if(l[sz].size()){
        int need = l[sz].front(); l[sz].pop();
        ans += qry(i) - qry(need);
        upd(1, need);
      }else{
        r[sz].push(i);
        upd(1, i);
      }
    }
  }
  return ans;
}

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