#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int nm[200100];
bool taken[200100];
int pir[200100];
vector<int> l[200100],r[200100];
int tre[200100];
int lowbit(int i){
return i&(-i);
}
int ct(int p){
int tp=0;
for (int i=p;i;i-=lowbit(i)){
tp+=tre[i];
}
return tp;
}
void ad(int p){
for (int i=p;i<=200100;i+=lowbit(i)){
tre[i]++;
}
}
long long count_swaps(std::vector<int> s) {
ll ans=0;
memset(taken,false,sizeof taken);
int n=s.size();
for (int i=1;i<=n*2;i++){
nm[i]=s[i-1];
int tp=nm[i];
if (tp<0) tp*=-1;
if (nm[i]<0){
if (!r[tp].empty()){
pir[i]=r[tp][0];
pir[r[tp][0]]=i;
r[tp].erase(r[tp].begin());
continue;
}
l[tp].push_back(i);
}else{
if (!l[tp].empty()){
pir[i]=l[tp][0];
pir[l[tp][0]]=i;
l[tp].erase(l[tp].begin());
continue;
}
r[tp].push_back(i);
}
}
for (int i=1;i<=n*2;i++){
if (taken[i]) continue;
int tp,tpa=0;
if (nm[i]>0){
tpa+=1;
}
tp=pir[i];
tpa+=tp-i-1;
tpa-=ct(tp-1)-ct(i);
taken[tp]=true;
ad(tp);
ans+=tpa;
//printf("%d %d\n",tp,tpa);
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
14 ms |
21592 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
14 ms |
21592 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
14 ms |
21592 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
10 ms |
21708 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
14 ms |
21592 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
14 ms |
21592 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |