Submission #1170571

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170571		wii	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	93 ms	138056 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 = 2e5 + 5;
queue<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 = 1; i <= n; ++i) {
        int v = s[i - 1];

        if (!pos[abs(v)].empty()) {
            int j = pos[abs(v)].front();
            if (s[j - 1] + v == 0) {
                pos[abs(v)].pop();
                l[j] = i;
            } else {
                pos[abs(v)].push(i);
            }
        } else {
            pos[abs(v)].push(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]);

        // cout << i << " " << j << " " << r + (s[i - 1] > s[j - 1]) << endl;

        upd(j, 1);
    }

    return ans;
}

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