Cod sursă (job #786642)

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#define MAXN 5003
#define MAXQ 5003
#define MOD 1000000007
#define int long long
using namespace std;
FILE *fin,*fout;

struct XYZ{
  int nrD,nrS;
};

int frec[MAXN];
XYZ aint[MAXN*4];
int sir[MAXN];
int rasp[MAXQ];
int din[MAXN][MAXN];
int q,n;

XYZ Suma(XYZ a,XYZ b){
  return {a.nrD+b.nrD,a.nrS+b.nrS};
}

XYZ Querry(int x,int y,int a,int b,int poz){
  int mij;

  if(y<a || b<x){
    return {0,0};
  }

  if(a<=x && y<=b){
    return aint[poz];
  }

  mij=(x+y)/2;
  return Suma(Querry(x    ,mij,a,b,poz*2  ),
              Querry(mij+1,y  ,a,b,poz*2+1));
}

void Update(int x,int y,int a,int poz){
  int mij;

  if(y<a || a<x){
    return;
  }

  if(a==x && y==a){
    if(aint[poz].nrD>0){
      aint[poz].nrD--;
      aint[poz].nrS++;
    }else{
      aint[poz].nrS--;
    }
    return;
  }

  mij=(x+y)/2;
  Update(x    ,mij,a,poz*2  );
  Update(mij+1,y  ,a,poz*2+1);
  aint[poz]=Suma(aint[poz*2],aint[poz*2+1]);
}

void ResetAint(int x,int y,int poz){
  int mij;

  if(x==y){
    aint[poz]={1,0};
    return;
  }

  mij=(x+y)/2;

  ResetAint(x    ,mij,poz*2  );
  ResetAint(mij+1,y  ,poz*2+1);

  aint[poz]=Suma(aint[poz*2],aint[poz*2+1]);

  return;
}

void Reset(){
  int i;

  for(i=1;i<=n;i++){
    frec[i]=0;
  }

  ResetAint(1,n,1);
}

void Init(){
  fin=fopen("dejavu.in","r");
  fout=fopen("dejavu.out","w");
  fscanf(fin,"%lld%lld",&n,&q);
}

void CitireLinie(){
  int i;

  for(i=0;i<n;i++){
    fscanf(fin,"%lld",&sir[i]);
  }
}

void Afis(){
  int i;

  for(i=0;i<q;i++){
    fprintf(fout,"%lld\n",rasp[i]);
  }

  fclose(fin);
  fclose(fout);
}

void CalcDin(){
  int nr,doub,unic,nef;

  for(doub=n/2;doub>=0;doub--){
    din[n][doub]=1;
  }

  for(nr=n-1;nr>=0;nr--){
    for(doub=nr/2;doub>=0;doub--){
      unic=nr-doub*2;
      nef=n-doub-unic;

      din[nr][doub]=din[nr+1][doub+1]*unic+
                    din[nr+1][doub  ]*nef;

      din[nr][doub]%=MOD;
    }
  }
}

signed main(){
  int t,nr,i;
  XYZ val;

  Init();
  CalcDin();

  for(t=0;t<q;t++){
    CitireLinie();
    Reset();
    nr=0;
    for(i=0;i<n;i++){
      val=Querry(1,n,1,sir[i]-1,1);

      rasp[t]+=din[i+1][nr  ]*val.nrD;
      rasp[t]%=MOD;
      rasp[t]+=din[i+1][nr+1]*val.nrS;
      rasp[t]%=MOD;

      Update(1,n,sir[i],1);
      frec[sir[i]]++;
      if(frec[sir[i]]==2){
        nr++;
      }
    }
  }

  Afis();

  return 0;
}