Cod sursă (job #799662)

#include <iostream>
#include <fstream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <algorithm>
#include <set>
//#include <time.h>
//#include <chrono>
#include <ctime>
#define MAXN 200'005
#define MAXK 9
#define RAD 450
using namespace std;

struct XYZ{
  int l,r,lung,lungNoua;
};

struct ABC{
  int l,r,k,kNou,lK,rK;
};

int sir[MAXN];
int sump[MAXN];
int valToPoz[RAD];
XYZ PozToInterval[MAXN];
ABC quer[MAXN];
vector <XYZ> marimi;
vector <int> lung[MAXN];
vector <int> gasim[MAXN];


///
int split=1;
clock_t start = clock();

void TimeCheck(char text[]){
  if(split%2==1){
    start = clock();
  }else{
    clock_t end = clock();
    printf("Time for %2d Split %s: %f\n",split/2,text,(double)(end - start) / CLOCKS_PER_SEC * 1000);
  }

  split++;
}


///

bool cmp(XYZ a, XYZ b){
  return a.lung<b.lung;
}
bool cmpReturn(XYZ a, XYZ b){
  return a.l<b.l;
}

int main(){
  ifstream cin("calin.in");
  ofstream cout("calin.out");
  int i,j,z,n,q,l,r,k,ans,last,newK;
  int cul,nr;

  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);


  TimeCheck("Citire");
  cin >> n >> q;

  for(i=1;i<=n;i++){
    cin >> sir[i];
  }
  TimeCheck("Citire");

  TimeCheck("Creare Marimi");

  cul=sir[1];
  nr=1;
  last=1;
  for(i=2;i<=n;i++){
    if(sir[i]==cul){
      nr++;
    }else{
      marimi.push_back({last,i-1,nr,0});
      lung[nr].push_back(marimi.size()-1);
      for(j=last;j<=i-1;j++){
        PozToInterval[j]={last,i-1,nr,0};
      }
      nr=1;
      cul=sir[i];
      last=i;
    }
  }



  marimi.push_back({last,n,nr,0});
  lung[nr].push_back(marimi.size()-1);
  for(j=last;j<=n;j++){
    PozToInterval[j]={last,n,nr,0};
  }

  TimeCheck("Creare Marimi");


  TimeCheck("Creare Lung Noi");

  int m=0;
  for(i=0;i<MAXN;i++){
    for(int aux : lung[i]){
      /*
      cout << marimi[i].l << " ";
      cout << marimi[i].r << " ";
      cout << marimi[i].lung << " ";
      cout << marimi[i].lungNoua << "\n";
      //*/
      XYZ per=marimi[aux];
      if(m==0){
        valToPoz[0]=per.lung;
        m=1;
      }else{
        if(valToPoz[m-1]!=per.lung){
          valToPoz[m]=per.lung;
          m++;
        }
      }
      marimi[aux].lungNoua=m-1;
    }
  }

  TimeCheck("Creare Lung Noi");

  /*for(i=0;i<marimi.size();i++){
    cout << marimi[i].l << " ";
    cout << marimi[i].r << " ";
    cout << marimi[i].lung << " ";
    cout << marimi[i].lungNoua << "\n";
  }*/

  /*for(i=1;i<=n;i++){
    cout << i << ": ";
    for(j=0;j<m;j++){
      cout << sump[i][j] << " ";
    }
    cout << "\n";
  }
  cout << "----\n";*/

  /*for(i=1;i<=n;i++){
    cout << i << ": ";
    for(j=0;j<m;j++){
      cout << sump[i][j] << " ";
    }
    cout << "\n";
  }*/

  TimeCheck("Creare Querry Noi");

  for(i=0;i<q;i++){
    cin >> l >> r >> k;


    int st,dr,mij;

    st=0;
    dr=m;
    while(dr-st>1){
      mij=(st+dr)/2;
      if(valToPoz[mij]<k){
        st=mij;
      }else{
        dr=mij;
      }
    }
    newK=st=0;
    if(valToPoz[st]<k){
      newK++;
    }

    quer[i]={l,r,k,newK,0,0};
    gasim[l].push_back(i*2);
    gasim[r].push_back(i*2+1);

    /*if(newK<m){
      ans=sump[r][newK]-sump[l][newK];

      XYZ aux=PozToInterval[l];

      if(aux.r-l+1>=k){
        ans++;
      }
      aux=PozToInterval[r];

      if(aux.lung>=k && r-aux.l+1<k && aux.l!=PozToInterval[l].l){
        ans--;
      }
    }else{
      ans=0;
    }

    cout << ans << "\n";*/
  }
  TimeCheck("Creare Querry Noi");


  TimeCheck("Facut Sume Partiale");
  j=0;

  for(i=1;i<=n;i++){
    if(j<marimi.size() && marimi[j].l==i){
      for(z=marimi[j].lungNoua;z>=0;z--){
        sump[z]++;
      }
      j++;
    }
    for(int z=0;z<gasim[i].size();z++){
      if(gasim[i][z]%2==1){
        quer[gasim[i][z]/2].rK=sump[quer[gasim[i][z]/2].kNou];
      }else{
        quer[gasim[i][z]/2].lK=sump[quer[gasim[i][z]/2].kNou];
      }
    }
  }
  TimeCheck("Facut Sume Partiale");


  TimeCheck("Afisare");
  for(i=0;i<q;i++){

    l=quer[i].l;
    r=quer[i].r;
    k=quer[i].k;
    newK=quer[i].kNou;
    int lk=quer[i].lK;
    int rk=quer[i].rK;

    if(newK<m){
      ans=rk-lk;

      XYZ aux=PozToInterval[l];

      if(aux.r-l+1>=k){
        ans++;
      }
      aux=PozToInterval[r];

      if(aux.lung>=k && r-aux.l+1<k && aux.l!=PozToInterval[l].l){
        ans--;
      }
    }else{
      ans=0;
    }

    cout << ans << "\n";
  }
  TimeCheck("Afisare");

  return 0;
}