Submission #757619

#	Time	Username	Problem	Language	Result	Execution time	Memory
757619		safaricola	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	170 ms	139456 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define rep(i,n) for(int i=1; i<=n; i++)
#define pb push_back
int fw[200010],n;
long long ans;
deque<int> nex[200010];
void upd(int x, int v){
    for(; x<200005; x+=x&-x)fw[x]+=v;
}
int sum(int x){
    int ret=0; 
    for(; x; x-=x&-x)ret+=fw[x];
    return ret;
}
long long count_swaps(vector<int> s) {
  n=s.size();
  rep(i,n)nex[100000+s[i-1]].pb(i);
  rep(i,n)upd(i,1);
  rep(i,n){
    int x=s[i-1];
    if(sum(i)-sum(i-1)==0)continue;
    if(x>0)ans++;
    nex[100000+x].pop_front();
    int j=nex[100000-x][0]; 
    nex[100000-x].pop_front();
    //cout<<j<<endl;
    ans+=sum(j)-sum(i)-1;
    upd(i,-1);
    upd(j,-1);
    //cout<<sum(j)-sum(j-1)<<endl;
    //cout<<ans<<endl;
  }
  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