Submission #741184

#	Time	Username	Problem	Language	Result	Execution time	Memory
741184		JakobZorz	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	154 ms	57604 KiB

shoes

#include "shoes.h"
#include <set>
using namespace std;
#define ll long long
#define POW 20

set<int> shoes[400000];
int n;
ll segtree[(2 << POW)+1];
int l[(2 << POW)+1], r[(2 << POW)+1];

ll init_node(int node, int l1, int r1) {
    l[node] = l1;
    r[node] = r1;
    int mid = (l1+r1)/2;
    if(node<(1<<POW))
        segtree[node] = init_node(2*node,l1,mid) + init_node(2*node+1,mid,r1);
    return segtree[node];
}

void update_node(int node) {
    if(node<(1<<POW))
        segtree[node]=segtree[2*node]+segtree[2*node+1];
    if(node!=1)
        update_node(node/2);
}

void set_dist(int i) {
    segtree[(1<<POW)+i]=0;
    update_node((1<<POW)+i);
}

ll get_dist_sum(int node, int i) {
    if(i<=l[node])
        return 0;
    if(i>=r[node])
        return segtree[node];
    
    return get_dist_sum(2*node, i) + get_dist_sum(2*node+1, i);
}

ll get_dist(int i){
    return segtree[(1<<POW)+i];
}

ll count_swaps(vector<int> s) {
    n = s.size();
    for(int i=0;i<n;i++)
        shoes[s[i]+200000].insert(i);
    for(int i=0;i<n;i++)
        segtree[(1<<POW) + i]=1;
    init_node(1, 0, 1<<POW);
    ll res=0;
    int pos1=0;
    while(pos1<n){
        int pos2=*shoes[200000-s[pos1]].begin();
        
        res+=get_dist_sum(1, pos2);
        if(s[pos1]<0)
            res--;
        set_dist(pos1);
        set_dist(pos2);
        shoes[200000-s[pos1]].erase(shoes[200000-s[pos1]].begin());
        shoes[200000+s[pos1]].erase(shoes[200000+s[pos1]].begin());
        
        while(get_dist(pos1)==0) pos1++;
    }
    
    return res;
}

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