Submission #889362

#	Time	Username	Problem	Language	Result	Execution time	Memory
889362		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	190 ms	274916 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

struct AIB {
    int n;
    vi V;

    AIB(int N) : n(N + 1), V(N + 1, 0) {}

    void update(int p, int v) {
        ++p;
        while(p < n) {
            V[p] += v;
            p += p & -p;
        }
    }

    int query(int p) {
        ++p;
        int re = 0;
        while(p) {
            re += V[p];
            p -= p & -p;
        }
        return re;
    }

    int query(int st, int dr) {
        if(st > dr) return 0;
        return query(dr) - (st ? query(st - 1) : 0);
    }
};

long long count_swaps(std::vector<int> s) {
    int n = s.size();
    AIB A(n);
    vector<deque<int> > St(n), Dr(n);
    for(int i = 0; i < n; ++i) {
        A.update(i, 1);
        if(s[i] > 0) {
            Dr[s[i]].push_back(i);
        } else {
            St[-s[i]].push_back(i);
        }
    }
    vector<int> used(n, 0);
    long long re = 0;
    for(int i = 0; i < n; ++i) {
        if(used[i]) continue;
        int pereche;
        if(s[i] > 0) {
            ++re;
            pereche = St[s[i]].front();
            St[s[i]].pop_front();
            Dr[s[i]].pop_front();
        } else {
            pereche = Dr[-s[i]].front();
            St[-s[i]].pop_front();
            Dr[-s[i]].pop_front();
        }
        re += A.query(i + 1, pereche - 1);
        
        used[i] = 1;
        used[pereche] = 1;
        A.update(i, -1);
        A.update(pereche, -1);
    }
	return re;
}

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