Submission #726468

#	Time	Username	Problem	Language	Result	Execution time	Memory
726468		hoainiem	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	104 ms	18772 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define nmax 200008
using namespace std;
int n, l[nmax], r[nmax], cur[nmax][2];
long long ans;
vector<int> st[nmax][2];
struct fenwick{
    int bit[nmax];
    void upd(int pos, int val){
        for (int i = pos; i <= n; i += (i & (-i)))
            bit[i] += val;
    }
    int get(int pos){
        int res = 0;
        for (int i = pos; i > 0; i -= (i & (-i)))
            res += bit[i];
        return res;
    }
    int get(int l, int r){
        return get(r) - get(l - 1);
    }
}tree;
int calc(int u, int v){
    int res = 0;
    tree.upd(u, -1);
    tree.upd(v, -1);
    res += tree.get(u, v);
    tree.upd(u, 2);
    return res;
}
long long count_swaps(std::vector<int> s) {
    n = s.size();
    memset(l, -1, sizeof(l));
    memset(r, -1, sizeof(r));
    ans = 0;
    for (int i = 1; i <= n; i++)
        tree.upd(i, 1);
    for (int i = 1; i <= (int)s.size(); i++){
        int u = s[i - 1], j = 1, v;
        if (u < 0){
            u = -u;
            j ^= 1;
        }
        j ^= 1;
        if (cur[u][j] < (int)st[u][j].size()){
            v = st[u][j][cur[u][j]++];
            r[v] = i;
            l[i] = v;
            ans += calc(v, i);
            if (s[i - 1] < 0)
                ans++;
        }
        else{
            j ^= 1;
            st[u][j].push_back(i);
        }
    }
	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