Auction solution (probably)

# include <algorithm>
# include <iostream>
# include <cstring>
# include <vector>
# include <cstdio>
# include <queue>
# define long long long // :-)
using namespace std;
long const lots=10000000;
template<class Pred> struct rmq;

/*.. snip "lrmq.hh" ..*/
/*.. snip "rsort.hh" ..*/

typedef pair<long,long> pill;
struct trill{
  long a,b,c;
  trill(long x=0,long y=0,long z=0):a(x),b(y),c(z){}
  bool operator<(trill const o)const{
    return a<o.a or a==o.a and (b<o.b or b==o.b and c<o.c);
  }
};

typedef vector<pill> vpill;
typedef vector<trill> vtrill;
rmq<less   <long>>** lo_q;
rmq<greater<long>>** hi_q;
long* orbit[3];
long* space;
long* assoc;
long *pvp,*wvp;
long pc,wc;

int main(){
  pvp=new long[lots*3+4];
  wvp=new long[lots*3+4];

  for (int i=3; i--;) orbit[i]=new long[lots+200];
  space=new long[lots+200];
  assoc=new long[lots*2+200];

  lo_q=new rmq<less   <long>> * [lots];
  hi_q=new rmq<greater<long>> * [lots];

  int testcase=1;
  int tsts; scanf("%d",&tsts); while (tsts--){
    long* pv=pvp+lots; // price value
    long* wv=wvp+lots; // weight value

    /* number of elements,
       first price,
       first weight,
       price mod,
       weight mod,
       price multiple,
       price add,
       weight multiple,
       weight add */
    long n, p1,w1, pod,wod, pm,pa, wm,wa;
    cin>>n>>p1>>w1>>pod>>wod>>pm>>pa>>wm>>wa;
    vector<trill> dn,up;

    // generate the sequence cycles
    pv[0]=p1; wv[0]=w1;
    pc=0,wc=0;
    {
      // might need up to n*2 elements at first (>M+1 and >K+1 never happen)
      int* lap=new int[pod+1]; for (long i=pod+1; i--;) lap[i]=0; lap[p1]=1;
      int* law=new int[wod+1]; for (long i=wod+1; i--;) law[i]=0; law[w1]=1;
      while (++pc<n*2) {pv[pc]=((pv[pc-1]*pm+pa)%pod)+1; if (lap[pv[pc]]) break; else lap[pv[pc]]=pc+1;}
      while (++wc<n*2) {wv[wc]=((wv[wc-1]*wm+wa)%wod)+1; if (law[wv[wc]]) break; else law[wv[wc]]=wc+1;}

      // calculate duplication count
      long pdup=lap[pv[pc]]-1;
      long wdup=law[wv[wc]]-1;
      if (pdup==pc+1) pdup=0; pdup=max(min(pdup,n-1),0ll);
      if (wdup==wc+1) wdup=0; wdup=max(min(wdup,n-1),0ll);

      // it's easier to know that length(pv) is not greater than length(wv)
      if (wc-wdup<pc-pdup){
        swap(wc,pc);
        swap(wv,pv);
        swap(pdup,wdup);
      }

      // unique elements are a special case
      for (long i=max(pdup,wdup); i--;)
        dn.push_back(trill(wv[i%wc],pv[i%pc],1)),
        up.push_back(trill(wv[i%wc],pv[i%pc],1)),
        --n;

      pv+=pdup, pc-=pdup;
      wv+=wdup, wc-=wdup;

      pc=min((long)pc,n);
      wc=min((long)wc,n);
      while (wdup>pdup and wdup--){
        ++pv, pv[pc-1]=pv[-1];
      }
      while (pdup>wdup and pdup--){
        ++wv, wv[wc-1]=wv[-1];
      }

      delete[] lap; delete[] law;
    }

    // the drift per generation is the reference list length mod the basis list length
    long drift=wc%pc;

    // build orbits
    int orbits=0, spaces=0;
    {
      bool* done=new bool[pc];
      for (int i=pc; i--;) done[i]=false;
      for (int i=0; i<pc; i++)
        if (not done[i]){
          orbit[2][orbits  ]=i;
          orbit[0][orbits  ]=spaces;
          for (int j=i; !done[j]; j=fastmod(j+drift,pc))
            done[j]=true, space[spaces]=pv[j], assoc[j*2]=orbits, assoc[j*2+1]=spaces++;
          orbit[1][orbits++]=spaces;
        }
      delete[] done;
    }

    // construct range minimum query tables
    for (int i=orbits; i--;)
      lo_q[i]=new rmq<   less<long>>(space+orbit[0][i],space+orbit[1][i]),
      hi_q[i]=new rmq<greater<long>>(space+orbit[0][i],space+orbit[1][i]);

    // find and count outliers
    for (long i=0; i<wc; i++){
      long id=i%pc;
      long count=(n-i+wc-1)/wc;
      ulong off=orbit[0][assoc[id*2]];
      long l=assoc[id*2+1]-off;
      long r=l+count;

      long period=(orbit[1][assoc[id*2]]-orbit[0][assoc[id*2]])*wc;
      long loop=orbit[1][assoc[id*2]]-orbit[0][assoc[id*2]];

      long u=lo_q[assoc[id*2]]->query(l,r); dn.push_back(trill(wv[i],space[u+off],(count-((loop+u-l)%loop)+loop-1)/loop));
      long v=hi_q[assoc[id*2]]->query(l,r); up.push_back(trill(wv[i],space[v+off],(count-((loop+v-l)%loop)+loop-1)/loop));
    }

    for (int i=orbits; i--;)
      delete lo_q[i], delete hi_[i];

    rad_sort(dn.begin(),dn.end());
    rad_sort(up.begin(),up.end());

    long red=0,rep=0;
    long sad=(1ll<<40ll),sap=-(1ll<<40ll);
    for (long i=0; i<dn.size(); i++){
       //if (dn[i].b<sad) printf("%lld: %lld * %lld\n",dn[i].a,dn[i].b,dn[i].c);
      if (dn[i].b<sad)
        sad=dn[i].b,
        red+=dn[i].c;
    }
    for (long i=up.size(); i--;){
      //if (up[i].b>sap) printf("%lld: %lld * %lld\n",up[i].a,up[i].b,up[i].c);
      if (up[i].b>sap)
        sap=up[i].b,
        rep+=up[i].c;
    }

    printf("Case #%d: %lld %lld\n",testcase++,rep,red);
  }

  for (long i=3; i--;) delete[] orbit[i];
  delete[] space;
  delete[] assoc;
  delete[] pvp;
  delete[] wvp;
  delete[] lo_q;
  delete[] hi_q;
}