Submission #691565

#	Time	Username	Problem	Language	Result	Execution time	Memory
691565		ismayil	Arranging Shoes (IOI19_shoes)	C++17	25 / 100	303 ms	31668 KiB

shoes

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAX = 2e5 + 5;
ll bit[MAX];
int n;
void update(int pos, ll val){
    for(int i = pos; i < n; i = i | (i + 1)) bit[i] += val;
}
ll query(int pos){
    ll res = 0;
    for(int i = pos; i >= 0; i = (i & (i + 1)) - 1) res += bit[i];
    return res;
}
ll query(int l, int r){
    if(l == 0) return query(r);
    return query(r) - query(l - 1);
}
ll count_swaps(vector<int> S){
    map<int, set<int>> m;
    n = S.size();
    for (int i = 0; i < n; i++)
    {
        m[S[i]].insert(i);
        update(i, 1);
    }
    
    ll ans = 0;
    for (int i = 0; i < n; i++)
    {
        if(query(i) == 0) continue;
        set<int> &s = m[-S[i]];
        auto it = s.upper_bound(i);
        
        if(it == s.end()) continue;
        int idx = (*it);
        if(S[i] >= 0) ans += query(i, idx - 1);
        else ans += query(i + 1, idx - 1);
        update(idx, -1);update(i, 1);
        s.erase(it);
        m[S[i + 1]].erase(i);
    }
    return ans;
}

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