| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 210903 | 2020-03-19T01:51:51 Z | Kevin_Zhang_TW | Job Scheduling (IOI19_job) | C++17 | 0 ms | 0 KB |
//#include "shoes.h"
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
const int maxn = 100100;
using ll = long long;
int v[maxn], n;
bool used[maxn];
void add(int i, int d) {
for (;i <= n;i += i & -i) v[i] += d;
}
int query(int i) {
int res = 0;
for (;i;i ^= i & -i) res += v[i];
return res;
}
vector<int> pos[2][maxn];
long long count_swaps(std::vector<int> s) {
ll res = 0;
n = s.size();
fill(used, used + n + 1, false);
fill(v, v + n + 1, 0);
for (int i = 0;i <= n;++i)
pos[0][i].clear(), pos[1][i].clear();
for (int i = n-1;i >= 0;--i)
pos[s[i] > 0][ abs(s[i]) ].pb(i);
for (int i = 0;i < n;++i) if (!used[i]) {
pos[s[i] > 0][ abs(s[i]) ].pop_back();
vector<int> &v = pos[s[i] < 0][ abs(s[i]) ];
res += (v.back()-i-1) - (query(v.back()-1) - query(i)) + (s[i] > 0);
used[ v.back() ] = true;
add( v.back(), 1);
v.pop_back();
}
return res;
}