This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "shoes.h"
class fin {
std::vector<int> T;
int lastone(int x) { return x & (x ^ (x-1)); }
public:
fin(int N) : T(N+1, 0) {}
void put(int pos, int val) {
for(int i = pos+1; i < (int)T.size(); i += lastone(i))
T[i] += val;
}
int get(int pos) {
int ret = 0;
for(int i = pos+1; i > 0; i -= lastone(i))
ret += T[i];
return ret;
}
};
long long count_swaps(std::vector<int> S) {
int N = S.size()/2;
std::vector<int> pos_l[100010], pos_r[100010];
for(int i = 0; i < 2*N; i++) {
if(S[i] < 0) pos_l[-S[i]].push_back(i);
else pos_r[S[i]].push_back(i);
}
long long ret = 0;
std::vector<int> next(2*N, 0);
for(int i = 1; i <= N; i++)
for(int j = 0; j < (int)pos_l[i].size(); j++)
next[std::min(pos_l[i][j], pos_r[i][j])] = std::max(pos_l[i][j], pos_r[i][j]);
fin F(2*N);
for(int i = 0; i < 2*N; i++) F.put(i, 1);
std::vector<char> live(2*N, 1);
for(int i = 0; i < 2*N; i++) if(next[i]) {
ret += F.get(next[i]-1) - F.get(i);
F.put(next[i], -1);
}
for(int i = 1; i <= N; i++)
for(int j = 0; j < (int)pos_l[i].size(); j++)
if(pos_l[i][j] > pos_r[i][j]) ret++;
return ret;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |