Submission #924955

#	Time	Username	Problem	Language	Result	Execution time	Memory
924955		hmm789	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	72 ms	22812 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define INF 1000000000000000000
#define MOD 998244353

int fw[200005];
void update(int x, int v) {
    for(x++; x < 200005; x += x&-x) fw[x] += v;
}
int query(int x) {
    int ans = 0;
    for(x++; x; x -= x&-x) ans += fw[x];
    return ans;
}
int query(int x, int y) {
    return query(y)-query(x-1);
}

long long count_swaps(std::vector<int> s) {
    long long ans = 0;
    int n = (int)s.size()/2;
    set<int> nxt[2*n+1];
    for(int i = 0; i < 2*n; i++) {
        nxt[s[i]+n].insert(i);
    }
    for(int i = 0; i < 2*n; i++) {
        if(query(i, i)) continue;
        int p = *nxt[-s[i]+n].begin();
        nxt[-s[i]+n].erase(nxt[-s[i]+n].begin());
        nxt[s[i]+n].erase(nxt[s[i]+n].begin());
        ans += p-i - query(i, p) - (s[i] < 0);
        update(i, 1);
        update(p, 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