Cod sursa(job #2602243)

Utilizator anabatAna Batrineanu anabat Data 16 aprilie 2020 13:49:54
Problema Litere Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <stdio.h>

#define NMAX 10000

int v[NMAX+1],aint[NMAX*4+1];

using namespace std;

void update(int nod,int st,int dr,int poz,int val){
  if(st==dr){
    aint[nod]+=val;
  }
  else{
    int mij=(st+dr)/2;
    if(poz<=mij){
      update(2*nod,st,mij,poz,val);
    }
    else if(poz>mij){
      update(2*nod+1,mij+1,dr,poz,val);
    }
    aint[nod]=aint[2*nod]+aint[2*nod+1];
  }
}

int query(int nod,int st,int dr,int left,int right){
  if(st==left&&dr==right){
    return aint[nod];
  }
  else{
    int mij=(st+dr)/2;
    if(right<=mij){
      return query(2*nod,st,mij,left,right);
    }
    else if(left>mij){
      return query(2*nod+1,mij+1,dr,left,right);
    }
    return query(2*nod,st,mij,left,mij)+query(2*nod+1,mij+1,dr,mij+1,right);
  }
}

int main()
{
  FILE *fin,*fout;
  fin=fopen("litere.in","r");
  fout=fopen("litere.out","w");

  int n,i,S;
  fscanf(fin,"%d\n",&n);
  char c;
  i=1;
  c=fgetc(fin);
  while(c!='\n'){
    v[i++]=(c-'a')+1;
    c=fgetc(fin);
  }
  S=0;
  for(i=1;i<=n;i++){
    update(1,1,NMAX,v[i],1);
    S+=query(1,1,NMAX,v[i]+1,NMAX);
  }
  fprintf(fout,"%d",S);

  fclose(fin);
  fclose(fout);

  return 0;
}