Submission #1170562

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170562		wii	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	1 ms	2632 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;

#define foru(i,a,b) for(int i = (a); i <= (b); ++i)
#define ford(i,a,b) for(int i = (a); i >= (b); --i)

const int MaxN = 1e5 + 5;
vector<int> pos[MaxN];
int l[MaxN];

int f[MaxN];
void upd(int u, int x) {
    for (; u < MaxN; u += u & -u)
        f[u] += x;
}

int get(int u) {
    int ans = 0;
    for (; u > 0; u -= u & -u)
        ans += f[u];
    return ans;
}

int get(int l, int r) {
    return get(r) - get(l - 1);
}

long long count_swaps(std::vector<int> s) {
    int n = s.size();
	for (int i = n; i >= 1; --i) {
        int v = s[i - 1];

        if (!pos[abs(v)].empty()) {
            int j = pos[abs(v)].back();
            if (s[j - 1] + v == 0) {
                pos[abs(v)].pop_back();
                l[i] = j;
            } else {
                pos[abs(v)].push_back(i);
            }
        } else {
            pos[abs(v)].push_back(i);
        }
	}

	int ans = 0;
    foru(i, 1, n) if (l[i]) {
        int j = l[i];

        int r = (j - i - 1) - get(i + 1, j - 1);
        ans += r;
        ans += (s[i - 1] > s[j - 1]);

        upd(j, 1);
    }

    return ans;
}

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