Cod sursa(job #1574985)

Utilizator emanuel_rRamneantu Emanuel emanuel_r Data 20 ianuarie 2016 23:37:53
Problema Litere Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#include<fstream>
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;


ofstream g("litere.out");

int AIB[10005], Index[10005], V[10005];
int n, pos;
char Buffer[100000];

void citeste_numar(int & nr)
{
    nr = 0;
    while(Buffer[pos] < '0' || Buffer[pos] > '9')
        pos++;
    while(Buffer[pos] >= '0' && Buffer[pos] <= '9')
        nr = nr*10 + Buffer[pos++] - '0';
}

void citeste_litera(int & nr)
{
    nr = 0;
    while(Buffer[pos] < 'a' || Buffer[pos] > 'z')
        pos++;
    nr = Buffer[pos++] - 'a' + 1;
}


void citire()
{
    freopen("litere.in", "r", stdin);
    fread(Buffer, 1, 100000, stdin);

    citeste_numar(n);
    for(int i=1; i<=n; i++){
        citeste_litera(V[i]);
    }
}

bool comp(int x, int y)
{
    if(V[x] != V[y])
        return V[x] < V[y];
    return x < y;
}

void Update(int poz)
{
    while(poz <= n){
        AIB[poz]++;
        poz += poz&(-poz);
    }
}

int Query(int poz)
{
    int sum = 0;
    while(poz > 0){
        sum += AIB[poz];
        poz -= poz&(-poz);
    }
    return sum;
}

void rez()
{
    int i, nrmut = 0;
    for(i=1; i<=n; i++)
        Index[i] = i;
    sort(Index + 1, Index + n + 1, comp);
    for(i=1; i<=n; i++){
        nrmut += Index[i] - Query(Index[i]) - 1;
        Update(Index[i]);
    }
    g<<nrmut<<"\n";
}

int main()
{
    citire();
    rez();
    return 0;
}