Submission #532810

#	Time	Username	Problem	Language	Result	Execution time	Memory
532810		makanhulia	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	145 ms	138564 KiB

shoes

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int N = 2e5;
const int nosus = 1e5;

queue<int>q[N + 5];
int BIT[N + 5];

int lsone(int x){
    return ((x) & (-x));
}

ll query(int x){
    x++;
    ll ret = 0;
    for(int i = x; i > 0; i -= lsone(i)){
        ret += BIT[i];
    }
    return ret;
}

ll query(int l, int r){
    return query(r) - query(l);
}

void update(int x, int val){
    x++;
    for(int i = x; i <= N; i += lsone(i)){
        BIT[i] += val;
    }
}
 
ll count_swaps(vector<int>v){
    int n = v.size();
    ll ans = 0;

    for(int i = 0; i < n; i++){
        int now = -v[i] + nosus;
        if(!q[now].empty()){
            int l = q[now].front();
            q[now].pop();
            ans += (i - l);
            ans -= (v[i] > 0);
            ans -= query(l, i);
            update(l, -1);
        } else{
            q[v[i] + nosus].push(i);
            update(i, 1);
        }
    }

    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