#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
const int NMAX = 100000;
vector<int> posDroites[NMAX+1];
int posGauche[NMAX];
int arbre[NMAX*3*2];
int push[NMAX*3*2];
pair<int, int> debFin[NMAX*3*2];
int iPosDroite[NMAX];
void init(int noeud, int deb, int fin)
{
debFin[noeud] = {deb, fin};
if(deb == fin-1) return;
int mil = (deb+fin)/2;
init(noeud*2, deb, mil);
init(noeud*2+1, mil, fin);
}
int trouver(int noeud, int deb, int fin)
{
arbre[noeud] += push[noeud];
if(debFin[noeud].first != debFin[noeud].second-1)
{
push[noeud*2] += push[noeud];
push[noeud*2+1] += push[noeud];
}
push[noeud] = 0;
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return 0;
if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin)) return arbre[noeud];
return trouver(noeud*2,deb, fin)+trouver(noeud*2+1, deb, fin);
}
int chang(int noeud, int deb, int fin)
{
arbre[noeud] += push[noeud];
if(debFin[noeud].first != debFin[noeud].second-1)
{
push[noeud*2] += push[noeud];
push[noeud*2+1] += push[noeud];
}
push[noeud] = 0;
if((debFin[noeud].first >= fin) || (debFin[noeud].second <= deb)) return arbre[noeud];
if((debFin[noeud].first >= deb) && (debFin[noeud].second <= fin))
{
push[noeud]++;
return arbre[noeud]+1;
}
return arbre[noeud] = chang(noeud*2,deb, fin)+chang(noeud*2+1, deb, fin);
}
long long count_swaps(std::vector<int> s) {
int nbVal = s.size()/2;
int nbG = 0;
for(int a = 0; a < s.size(); a++)
{
int i = s[a];
if(i > 0)
{
posDroites[i].push_back(a);
}
else
{
posGauche[nbG] = a;
nbG++;
}
}
//cout << "okmj" << endl;
long long somme = 0;
//int decalage = 0;
init(1, 0, s.size());
for(int iPair = 0; iPair < nbVal; iPair++)
{
int pos1 = posGauche[iPair]+trouver(1, posGauche[iPair], posGauche[iPair]+1);
//cout << posGauche[iPair] << endl;
// cout << pos1 << " ";
somme += (pos1-iPair*2);
int type = abs(s[posGauche[iPair]]);
//cout << posDroites[type].front()+trouver(1, posDroites[type].front(), posDroites[type].front()+1) << endl;
chang(1, 0, posGauche[iPair]);
int pos2 = posDroites[type][iPosDroite[type]]+trouver(1, posDroites[type][iPosDroite[type]], posDroites[type][iPosDroite[type]]+1);
somme += (pos2-(iPair*2+1));
// cout << pos2 << endl;
// cout << trouver(1, posDroites[type][iPosDroite[type]], posDroites[type][iPosDroite[type]]+1) << endl;
chang(1, 0, posDroites[type][iPosDroite[type]]);
iPosDroite[type]++;
//somme += (pos2-pos1)-1;
//cout << "res : " << ((pos1-iPair*2)) << " " << (pos2-(iPair*2+1)) << " " << somme << endl;
}
return somme;
}
Compilation message
sculpture.cpp:1:10: fatal error: shoes.h: No such file or directory
1 | #include "shoes.h"
| ^~~~~~~~~
compilation terminated.
