Submission #418620

#	Time	Username	Problem	Language	Result	Execution time	Memory
418620		jasmin	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	731 ms	149284 KiB

shoes

#include<bits/stdc++.h>
#include "shoes.h"

using namespace std;
vector<int> seg;

int get(int l, int r, int n, int ql, int qr){
    if(r<=ql || l>=qr) return 0;
    if(l>=ql && r<=qr) return seg[n];
    int m=l+(r-l)/2;
    return get(l, m, n*2+1, ql, qr)+get(m, r, n*2+2, ql, qr);
}

int set_value(int l, int r, int n, int i, int x){
    if(r<=i || l>i) return seg[n];
    if(l+1==r) return seg[n]=x;
    int m=l+(r-l)/2;
    return seg[n]=set_value(l, m, n*2+1, i, x)+set_value(m, r, n*2+2, i, x);
}

long long count_swaps(std::vector<int> s) {
    int a=s.size();
    seg.assign(4*a, 0);
    for(int i=0; i<a; i++){
        set_value(0, a, 0, i, 1);
    }

    map<int, queue<int> >l;
    map<int, queue<int> >r;
    for(int i=0; i<a; i++){
        if(s[i]<0){
            l[-s[i]].push(i);
        }
        else{
            r[s[i]].push(i);
        }
    }

    long long ans=0LL;
    vector<bool> done(a);
    for(int i=0; i<a; i++){
        if(done[i]) continue;
        if(s[i]<0){
            l[-s[i]].pop();
            int next=r[-s[i]].front();
            r[-s[i]].pop();
            ans+=get(0, a, 0, i, next)-1;
            set_value(0, a, 0, next, 0);
            done[next]=true;
        }
        else{
            r[s[i]].pop();
            int next=l[s[i]].front();
            l[s[i]].pop();
            ans+=get(0, a, 0, i, next);
            set_value(0, a, 0, next, 0);
            done[next]=true;
        }
    }
    return ans;

}

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