Submission #751232

#	Time	Username	Problem	Language	Result	Execution time	Memory
751232		kusmetliq	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	247 ms	75468 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
long long fen[200000];
void upd(int x,int v) {
    x++;
    while(x<200000) {
        fen[x]+=v;
        x+=x&(-x);
    }
}
long long ask(int x) {
    x++;
    long long sum=0;
    while(x>0) {
        sum+=fen[x];
        x-=x&(-x);
    }
    return sum;
}
long long count_swaps(vector<int> s) {
    int n=s.size();
    map<int,deque<int>>m;
    for(int i=0;i<n;i++) {
        upd(i,1);
        if(s[i]>0) {
            m[s[i]].push_back(i);
        }
    }
    long long ans=0;
    for(int i=0;i<n;i++) {
        if(s[i]<0) {
            int v=-s[i];
            upd(i,-1);
            ans+=ask(i);
            int 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: 0 / 20
• Subtask 4: 0 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15