Sto cercando di risolvere paletta usando un segment tree.
Al momento faccio 22.6 su 100 (riesco a distinguere quando esiste una soluzione ma non sempre risulta corretta e nell’ultimo subtask 4 su 5 vanno in tle).
La mia idea era di dividere l’array in 2 sub-array di numeri pari e dispari (affinche’ sia risolvibile il problema, ogni elemento deve essere pari/dispari come il suo indice(0-based)).
Successivamente contare il numero di swap che bisogna fare per ordinarli.
Avevo in mente di farlo con un segment tree e quindi conto per ogni numero quanti numeri prima di lui sono piu’ grandi.
Ma non so perche’ non funziona, some help?
EDIT:
trovato l’errore ed ora mi fa 94/100 ma mi hanno detto che con segment tree non si riesce a risolvere questo problema.
Codice:
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
using namespace std;
#define PB push_back
typedef vector<int> vi;
const int mxN = 1500000;
int n;
vi t(mxN*4,0);
void upd( int l1, long long x, int i=1, int l2=0, int r2=n-1)
{
if(l2==r2){
t[i] = x;
return;
}
int m2 = (l2+r2)/2;
if(l1 >= l2 && l1 <= m2)
upd(l1, x, 2*i, l2, m2);
else
upd(l1, x, 2*i+1, m2+1, r2);
t[i] = t[2*i] + t[2*i+1];
}
int qry(int l1, int r1, int i=1, int l2=0, int r2=n-1){
if (l1 > r2 || r1 < l2)
return 0;
if(l1 <= l2 && r2 <= r1)
return t[i];
int m2 = (l2+r2)/2;
int q1 = qry(l1, r1, 2*i, l2, m2);
int q2 = qry(l1, r1, 2*i+1, m2+1, r2);
return q1 + q2;
}
long long paletta_sort(int N, int V[]){
long long ris=0;
vi p,d;
n=N;
for (int i = 0; i < n; ++i){
if(i%2!=V[i]%2)
return -1;
if(V[i]%2==1)
d.PB(V[i]);
else
p.PB(V[i]);
}
for(int i=0; i<d.size(); ++i){
ris += qry(d[i]+1, n-1);
upd(d[i], 1);
}
fill(t.begin(), t.end(), 0);
for(int i=0; i<p.size(); ++i){
ris += qry(p[i]+1, n-1);
upd(p[i], 1);
}
return ris;
}