#include <iostream>
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first
#define b second
#include "shoes.h"
llo tree[100005];
long long n;
llo ss(llo i){
llo tot=0;
while(i<=2*n){
tot+=tree[i];
i+=(i&-i);
}
return tot;
}
void u(llo j){
while(j>0){
tree[j]+=1;
j-=(j&-j);
}
}
long long count_swaps(vector<int> s){
n=s.size();
n/=2;
memset(tree,0,sizeof(tree));
vector<llo> aa[n+1];
vector<llo> bb[n+1];
for(llo i=0;i<2*n;i++){
if(s[i]<0){
aa[-s[i]].pb(i);
}
else{
bb[s[i]].pb(i);
}
}
llo ind[n+1];
llo ind2[n+1];
long long tot=0;
memset(ind,0,sizeof(ind));
memset(ind2,0,sizeof(ind2));
llo vis[2*n];
memset(vis,0,sizeof(vis));
for(llo i=0;i<2*n;i++){
//cout<<i<<endl;
if(vis[i]==1){
continue;
}
else{
if(s[i]<0){
llo ind3=ind[abs(s[i])];
llo j=aa[abs(s[i])][ind3];
llo k=bb[abs(s[i])][ind3];
llo co=ss(k+1)-ss(j+1);
tot+=(k-j-1)-co;
vis[j]=1;
vis[k]=1;
u(k+1);
u(j+1);
}
else{
llo ind3=ind2[abs(s[i])];
llo j=aa[abs(s[i])][ind3];
llo k=bb[abs(s[i])][ind3];
llo co=ss(j+1)-ss(k+1);
// cout<<co<<endl;
tot+=(j-k)-co;
vis[j]=1;
vis[k]=1;
u(j+1);
u(k+1);
}
ind[abs(s[i])]+=1;
ind2[abs(s[i])]+=1;
}
}
return tot;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1144 KB |
Output is correct |
2 |
Correct |
6 ms |
1144 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1144 KB |
Output is correct |
2 |
Correct |
6 ms |
1144 KB |
Output is correct |
3 |
Correct |
5 ms |
1148 KB |
Output is correct |
4 |
Correct |
6 ms |
1144 KB |
Output is correct |
5 |
Correct |
6 ms |
1144 KB |
Output is correct |
6 |
Correct |
5 ms |
1144 KB |
Output is correct |
7 |
Incorrect |
6 ms |
1140 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1144 KB |
Output is correct |
2 |
Correct |
6 ms |
1144 KB |
Output is correct |
3 |
Incorrect |
6 ms |
1144 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
1144 KB |
Output is correct |
2 |
Incorrect |
6 ms |
1016 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1144 KB |
Output is correct |
2 |
Correct |
6 ms |
1144 KB |
Output is correct |
3 |
Correct |
5 ms |
1148 KB |
Output is correct |
4 |
Correct |
6 ms |
1144 KB |
Output is correct |
5 |
Correct |
6 ms |
1144 KB |
Output is correct |
6 |
Correct |
5 ms |
1144 KB |
Output is correct |
7 |
Incorrect |
6 ms |
1140 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
1144 KB |
Output is correct |
2 |
Correct |
6 ms |
1144 KB |
Output is correct |
3 |
Correct |
5 ms |
1148 KB |
Output is correct |
4 |
Correct |
6 ms |
1144 KB |
Output is correct |
5 |
Correct |
6 ms |
1144 KB |
Output is correct |
6 |
Correct |
5 ms |
1144 KB |
Output is correct |
7 |
Incorrect |
6 ms |
1140 KB |
Output isn't correct |
8 |
Halted |
0 ms |
0 KB |
- |