#include<bits/stdc++.h>
//#include<shoes.h>
using namespace std;
const int NAX = 1e5 + 5;
struct Hash{
size_t operator()(const pair<int , int> &x) const{
return ((long long)x.first) ^ (((long long)x.second) << 32);
}
};
// fenwick tree to count range sums (+0 , +1 , +2)
int f[2 * NAX + 1];
void update(int idx , int u){
++idx;
while(idx <= N){
f[idx] += u;
idx += idx & (-idx);
}
}
long long sum(int idx){
long long sum = 0;
++idx;
while(idx){
sum += f[idx];
idx -= idx & (-idx);
}
return sum;
}
unordered_map<pair<long , long> , bool , Hash> paired , px , nx;
queue<int> q[NAX];
long long count_swaps(vector<int> S){
int N = S.size();
long long ans = 0;
for(int i = 1; i <= N; ++i){
px[{i , 1}] = false;
nx[{i , -1}] = false;
}
// update BIT
for(int i = 0; i < N; ++i){
update(i , 1);
}
for(int i = 0; i < N; ++i){
int x = abs(S[i]);
int k = S[i];
// when queue is empty
if(q[x].empty()){
if(k > 0){
q[x].push(i);
//positive x's are in the queue
px[{x , 1}] = true;
nx[{x , -1}] = false;
}
else {
q[x].push(i);
// negative x's are int the queue
nx[{x , -1}] = true;
px[{x , 1}] = false;
}
} else if(px[{x , 1}]){
if(k < 0){
ans += (sum(i) - sum(q[x].front() - 1) - 1);
update(i , -1);
if(q[x].front()){
update(q[x].front() - 1 , 1);
}
q[x].pop();
} else {
q[x].push(i);
}
} else if(nx[{x , -1}]){
if(k > 0){
ans += (sum(i) - sum(q[x].front() - 1) - 2);
update(q[x].front() , -1);
update(i - 1 , 1);
q[x].pop();
} else {
q[x].push(i);
}
}
if(q[x].empty()){
px[{x , 1}] = false;
nx[{x , -1}] = false;
}
}
return ans;
}
Compilation message
shoes.cpp: In function 'void update(int, int)':
shoes.cpp:19:18: error: 'N' was not declared in this scope
while(idx <= N){
^
