Cod sursa(job #2777043)

Utilizator popescuadrianpopescuadrian popescuadrian Data 21 septembrie 2021 22:12:58
Problema Schi Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.78 kb
#include <fstream>

using namespace std;
ifstream cin ("circlecross.in");
ofstream cout ("circlecross.out");
int n;
long long bit[100005];
int fre[100005];
void update (int poz,int val)
{
    while(poz<=2*n)
    {
        bit[poz]=bit[poz]+val;
        poz=poz+(poz&-poz);
    }
}
int pq (int poz)
{
    long long suma=0;
    while(poz)
    {
        suma=suma+bit[poz];
        poz=poz-(poz&-poz);
    }
    return suma;
}
int main()
{
    long long i,j,k,suma=0,x;
    cin>>n;
    for(i=1;i<=2*n;i++)
    {
        cin>>x;
        if(fre[x]==0)
        {
            fre[x]=i;
            update(i,1);
        }
        else
        {
            suma=suma+pq(i)-pq(fre[x]);
            update(fre[x],-1);
        }
    }
    cout<<suma;
    return 0;
}