Submission #145541

#	Time	Username	Problem	Language	Result	Execution time	Memory
145541		Sarah_Mokhtar	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	449 ms	26012 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,M=(N<<4),OO=0x3f3f3f;
int pos[N],BIT[M],n;
void update(int idx,int val){
	++idx;
    while(idx<=n){
        BIT[idx]+=val;
        idx+=(idx&-idx);
    }
}
ll query(int r){
    ll res=0;
    ++r;
	while(r>0){
        res+=BIT[r];
        r-=(r&-r);
    }
    return res;
}
ll count_swaps(vector<int>s){
    map<int,vector<int>>m;
    ll ret=0;
    n=s.size();
    for(int i=0;i<n;++i)
        update(i,1);
    for(int i=n-1;i>=0;--i)
        m[s[i]].push_back(i);
    for(int i=0;i<n;++i){
        if(query(i)-query(i-1)!=1) continue;
        int k=m[-s[i]].back();
        m[s[i]].pop_back();
        m[-s[i]].pop_back();
        update(i,-1);
        update(k,-1);
        ret+=query(k)-query(i);
        if(s[i]>0) ++ret;

    }
    return ret;
}

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