Submission #1021749

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021749		nisanduu	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	0 ms	348 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void update(vector<ll>&seg,ll ind,ll l,ll r,ll givenpos){
    if(l==r){
        seg[ind]+=1;
        return;
    }
    ll mid = l + (r-l)/2;
    if(mid>=givenpos){
        update(seg,2*ind+2,mid+1,r,givenpos);
    }else{
        update(seg,2*ind+1,l,mid,givenpos);
    }
    seg[ind] = seg[2*ind+1] + seg[2*ind+2];
    return;
}

ll query(vector<ll>&seg,ll ind,ll l,ll r,ll left,ll right){
    if(l>right||r<left) return 0;
    if(l<=left&&r>=right) return seg[ind];
    ll mid = l + (r-l)/2;
    return query(seg,2*ind+1,l,mid,left,right) + query(seg,2*ind+2,mid+1,r,left,right);
}

long long count_swaps(std::vector<int> s) {
    long long ans = 0;
    long long n = s.size();
    vector<vector<ll>> left(n+10),right(n+10);
    for(ll i=0;i<n;i++){
        ll sz = abs(s[i]);
        if(s[i]<0){
            left[sz].push_back(-i);
        }else{
            right[sz].push_back(-i);
        }
    }
    for(ll i=0;i<n;i++){
        sort(left[i].begin(),left[i].end());
        sort(right[i].begin(),right[i].end());
    }
    vector<ll> seg(6*n);
    map<ll,ll> used;
    for(ll i=0;i<n;i++){
        if(!used[i]){
            ll sz = abs(s[i]);
            ll tmpA = 0;
            if(s[i]<0){
                ll pos = right[sz].back();
                pos *= -1;
                right[sz].pop_back();
                left[sz].pop_back();
                ll am = pos - i;
                am = am - query(seg,0,0,n-1,i,pos);
                update(seg,0,0,n-1,pos);
                used[pos]=1;
                used[i]=1;
                tmpA = am;
            }else{
                ll pos = left[sz].back();
                pos *= -1;
                right[sz].pop_back();
                left[sz].pop_back();
                ll am = pos - i;
                am = am - query(seg,0,0,n-1,i,pos);
                update(seg,0,0,n-1,pos);
                used[pos]=1;
                used[i]=1;
                tmpA = am;
            }
            
            if(i%2==0){
                if(s[i]>0) tmpA++;
            }else{
                if(s[i]<0) tmpA++;
            }
            ans+=tmpA;
        }
    }
     
	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