Submission #751325

#	Time	Username	Problem	Language	Result	Execution time	Memory
751325		kusmetliq	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	1 ms	212 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) {
    int n=s.size();
    long long ans=0;
    map<int,deque<int>>m;
    for(int i=0;i<n;i++) {
        m[s[i]].push_back(i);
    }
    for(int i=0;i<n;i++) {
        while(m[s[i]].size()>0) {
            int ind=m[-abs(s[i])].front();
            int indsecond=m[abs(s[i])].front();
            ans+=abs(ind-indsecond);
            if(ind<indsecond)ans--;
            else ans++;
            m[s[i]].pop_front();
            m[-s[i]].pop_front();
        }
    }
    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