#include "shoes.h"
#include <cstdio>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;
long long int seg[500000];
void update(long long int s,long long int e,long long int u,long long int ind){
if(u<s || u>e){
return;
}
if(s==e && s==u){
seg[ind]=1;
return;
}
long long int mid=(s+e)/2;
update(s,mid,u,ind*2);
update(mid+1,e,u,ind*2+1);
seg[ind]=seg[ind*2]+seg[ind*2+1];
}
long long int query(long long int s,long long int e , long long int qs,long long int qe,long long int ind){
if(qs<=s && e<=qe){
return seg[ind];
}
if(qs>e || qe<s){
return 0;
}
long long int mid=(s+e)/2;
long long int p1=query(s,mid,qs,qe,ind*2);
long long int p2=query(mid+1,e,qs,qe,ind*2+1);
return p1+p2;
}
long long count_swaps(std::vector<long long int> s) {
vector < long long int > row;
vector < long long int > row2;
vector < vector < long long int > > l(200000,row);
vector < vector < long long int > > r(200000,row2);
long long int li[200000+1]={};
long long int ri[200000+1]={};
for(long long int i=0;i<s.size();i++){
if(s[i]>0){
r[s[i]].push_back(i);
}
else
l[-s[i]].push_back(i);
}
long long int ans=0;
/// n log n
long long int v[200000]={};
for(long long int i=0;i<s.size();i++){
long long int cou=0;
if(v[i]==1){
continue;
}
long long int f=-s[i];
if(f>0){
li[f]++;
long long int start=i;
long long int e=r[f][ri[f]];
ri[f]++;
long long int q=query(1,s.size(),start+1,e+1,1);
v[start]=1;
v[e]=1;
update(1,s.size(),start+1,1);
update(1,s.size(),e+1,1);
// cout<<q<<endl;
cou=cou + e-start-1-q;
}
else{
cou=1;
ri[-f]++;
long long int start=i;
long long int e=l[-f][li[-f]];
li[-f]++;
long long int q=query(1,s.size(),start+1,e+1,1);
v[start]=1;
v[e]=1;
update(1,s.size(),start+1,1);
update(1,s.size(),e+1,1);
// cout<<q<<endl;
cou=cou + e-start-1-q;
}
ans+=cou;
}
return ans;
}
Compilation message
shoes.cpp: In function 'long long int count_swaps(std::vector<long long int>)':
shoes.cpp:55:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
55 | for(long long int i=0;i<s.size();i++){
| ~^~~~~~~~~
shoes.cpp:67:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for(long long int i=0;i<s.size();i++){
| ~^~~~~~~~~
/tmp/cc7hduGu.o: In function `main':
grader.cpp:(.text.startup+0x26a): undefined reference to `count_swaps(std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
