Cod sursă (job #786721)

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

struct XYZ{
  int nrD,nrS;
};

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

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

XYZ Querry(int poz){
  XYZ ans;

  ans={0,0};

  while(poz){
    ans=Suma(ans,aib[poz]);
    poz&=poz-1;
  }

  return ans;
}

void UpdateAib(int poz,XYZ val){
  do{
    aib[poz]=Suma(aib[poz],val);
    poz+=poz&-poz;
  }while(poz<=n);
}

void ResetAib(){
  int i,j;

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

  for(i=1;i<=n;i++){
    j=i+(i&-i);
    if(j<=n){
      aib[j]=Suma(aib[i],aib[j]);
    }
  }
}

void Reset(){
  int i;

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

  ResetAib();
}

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

void CitireLinie(){
  int i;

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

void AfisFinal(){
  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,updVal;

  Init();
  CalcDin();

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

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

      frec[sir[i]]++;
      if(frec[sir[i]]==2){
        nr++;
        updVal={0,-1};
      }else{
        updVal={-1,1};
      }
      UpdateAib(sir[i],updVal);
    }
  }

  AfisFinal();

  return 0;
}