Submission #751237

#	Time	Username	Problem	Language	Result	Execution time	Memory
751237		kusmetliq	Arranging Shoes (IOI19_shoes)	C++14	45 / 100	253 ms	75452 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long fen[500000];
void upd(long long x,long long v) {
    x++;
    while(x<500000) {
        fen[x]+=v;
        x+=x&(-x);
    }
}
long long ask(long long x) {
    x++;
    long long sum=0;
    while(x>0) {
        sum+=fen[x];
        x-=x&(-x);
    }
    return sum;
}
long long count_swaps(vector<int> s) {
    long long n=s.size();
    map<long long,deque<long long>>m;
    for(long long i=0;i<n;i++) {
        upd(i,1);
        if(s[i]>0) {
            m[s[i]].push_back(i);
        }
    }
    long long ans=0;
    for(long long i=0;i<n;i++) {
        if(s[i]<0) {
            long long v=-s[i];
            upd(i,-1);
            ans+=ask(i);
            long long ind=m[v].front();
            m[v].pop_front();
            upd(ind,-1);
            ans+=ask(ind);
        }
    }
    return ans;
}

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