Submission #1138844

#	Time	Username	Problem	Language	Result	Execution time	Memory
1138844		Rufat	Arranging Shoes (IOI19_shoes)	C++20	0 / 100	0 ms	324 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
struct Fenwick {
    int n;
    vector<long long> fenw;
    Fenwick(int n) : n(n), fenw(n+1, 0) {}
    void update(int i, long long diff){
        for(++i; i <= n; i += i & -i) fenw[i] += diff;
    }

    long long query(int i){
        long long s = 0; 
        for(++i; i > 0; i -= i & -i) s += fenw[i];
        return s;
    }
    
    // Query the sum in [l, r]
    long long rangeQuery(int l, int r){
        if(l > r) return 0;
        return query(r) - query(l-1);
    }
};
long long count_swaps(std::vector<int> s) {
    int n = (int)s.size();
    Fenwick fenw(n);
    for(int i = 0; i < n; i++){
        fenw.update(i, 1);
    }
    unordered_map<int, vector<int>> leftStack;
    long long ans = 0;
    for(int i = 0; i < n; i++){
        int size = abs(s[i]);
        if(s[i] < 0){
            leftStack[size].push_back(i);
        } 
        else {
            int L = leftStack[size].back();
            leftStack[size].pop_back();
            int R = i;
            int leftPos = min(L, R), rightPos = max(L, R);
            long long between = fenw.rangeQuery(leftPos+1, rightPos-1);
            ans += between;
            fenw.update(L, -1);
        }
    }
    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