SPOJ POSTERS (WA)

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N (10000000)
#define MAX_P (40000)

typedef struct { int num, upd; } node;
typedef struct { int l, r; } query;

node st[4*MAX_N];
query qs[MAX_P];
int xs[2*MAX_P];
bool sn[MAX_P+1];

int max(int x, int y) { return x > y ? x : y; }

int cmp(const void * arg1, const void * arg2) {
  return *(const int *)arg1 - *(const int *)arg2;
}

int rem_dups(int * xs, int n) {
  int i,j;

  for ( j=0,i=1; i < n; ++i ) {
    for ( j=j+1; j < n && xs[j] == xs[j-1]; ++j );
    if ( j < n ) xs[i] = xs[j];
    else break;
  }
  return i;
}

void update(int p, int l, int r) {
  if ( !st[p].upd ) return;
  st[p].num = st[p].upd;
  if ( l != r )
    st[2*p].upd = st[2*p+1].upd = st[p].num;
  st[p].upd = 0;
}

void st_update(int p, int l, int r, int i, int j, int x) {
  update(p, l, r);
  if ( r < i || l > j )
    return;
  if ( l >= i && r <= j ) {
    st[p].upd = x;
    update(p, l, r);
    return;
  }
  st_update(2*p, l, (l+r)/2, i, j, x);
  st_update(2*p+1, (l+r)/2 + 1, r, i, j, x);
}

int st_query(int p, int l, int r, int i, int j) {
  int lt, rt;

  update(p, l, r);
  if ( r < i || l > j )
    return 0;
  if ( l >= i && r <= j )
    return st[p].num;
  lt = st_query(2*p, l, (l+r)/2, i, j);
  rt = st_query(2*p+1, (l+r)/2+1, r, i, j);
  return max(lt, rt);
}

int main() {
  int i,n,q,t,x,ctr,acc;

  scanf("%d", &t);
  while ( t-- ) {
    memset(sn, 0, (MAX_P+1)*sizeof(*sn));
    scanf("%d", &q);
    for ( i=ctr=0; i < q; ++i ) {
      scanf("%d %d", &qs[i].l, &qs[i].r);
      xs[ctr++] = qs[i].l, xs[ctr++] = qs[i].r;
    }
    qsort(xs, 2*q, sizeof(*xs), cmp);
    n = rem_dups(xs, 2*q);
    for ( i=0; i < q; ++i ) {
      int l = (int *)bsearch(&qs[i].l, xs, n, sizeof(*xs), cmp) - xs;
      int r = (int *)bsearch(&qs[i].r, xs, n, sizeof(*xs), cmp) - xs;
      st_update(1, 0,  2*MAX_P, l, r, i+1);
    }
    for ( i=acc=0; i < 2*q; ++i )
      if ( (x = st_query(1, 0, 2*MAX_P, i, i)) )
        if ( !sn[x] )
          sn[x] = true, acc += 1;
    printf("%d\n", acc);
  }
  return EXIT_SUCCESS;
}