#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
int op[100000],tree[300000];
unordered_map<int,int>p;
vector<int>lft;
void build(int id,int l,int r){
if(l==r){
tree[id]=1;
return;
}
build(id*2,l,(l+r)/2);
build(id*2+1,(l+r)/2+1,r);
tree[id]=tree[id*2]+tree[id*2+1];
}
long long query(int id,int l,int r,int L,int R){
if(r<L || R<l){
return (long long)0;
}
if(L<=l && r<=R){
return (long long)tree[id];
}
return query(id*2,l,(l+r)/2,L,R)+query(id*2+1,(l+r)/2+1,r,L,R);
}
void update(int id,int l,int r,int index){
if(l==r){
tree[id]=0;
return;
}
if(index<=(l+r)/2){
update(id*2,l,(l+r)/2,index);
}
else update(id*2+1,(l+r)/2+1,r,index);
tree[id]=tree[id*2]+tree[id*2+1];
}
long long count_swaps(vector<int> s) {
int n=s.size();
for(int i=0;i<s.size();i++){
if(p[-s[i]]!=0){
op[p[-s[i]]-1]=i;
p[-s[i]]=0;
}
else{
p[s[i]]=i+1;
lft.push_back(i);
}
}
long long ans=0;
build(1,0,n-1);
for(int i=0;i<lft.size();i++){
int l=lft[i],r=op[lft[i]];
if(s[l]>0) ans++;
ans+=(query(1,0,n-1,l,r));
ans-=2;
update(1,0,n-1,r);
}
return ans;
}
Compilation message
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:38:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i=0;i<s.size();i++){
| ~^~~~~~~~~
shoes.cpp:50:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for(int i=0;i<lft.size();i++){
| ~^~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
0 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
256 KB |
Output is correct |
4 |
Incorrect |
1 ms |
256 KB |
Output isn't correct |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
256 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
0 ms |
256 KB |
Output is correct |
4 |
Correct |
1 ms |
256 KB |
Output is correct |
5 |
Correct |
0 ms |
256 KB |
Output is correct |
6 |
Correct |
1 ms |
384 KB |
Output is correct |
7 |
Correct |
1 ms |
384 KB |
Output is correct |
8 |
Correct |
1 ms |
384 KB |
Output is correct |
9 |
Correct |
0 ms |
256 KB |
Output is correct |
10 |
Correct |
1 ms |
512 KB |
Output is correct |
11 |
Correct |
1 ms |
256 KB |
Output is correct |
12 |
Correct |
1 ms |
384 KB |
Output is correct |
13 |
Correct |
1 ms |
384 KB |
Output is correct |
14 |
Incorrect |
1 ms |
384 KB |
Output isn't correct |
15 |
Halted |
0 ms |
0 KB |
- |