Submission #953710

#	Time	Username	Problem	Language	Result	Execution time	Memory
953710		Trisanu_Das	Arranging Shoes (IOI19_shoes)	C++17	0 / 100	71 ms	135024 KiB

shoes

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

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