SHARE
TWEET

SPOJ POSTERS (WA)

a guest Feb 20th, 2015 263 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdbool.h>
  2. #include <stdio.h>
  3. #include <stdlib.h>
  4. #include <string.h>
  5.  
  6. #define MAX_N (10000000)
  7. #define MAX_P (40000)
  8.  
  9. typedef struct { int num, upd; } node;
  10. typedef struct { int l, r; } query;
  11.  
  12. node st[4*MAX_N];
  13. query qs[MAX_P];
  14. int xs[2*MAX_P];
  15. bool sn[MAX_P+1];
  16.  
  17. int max(int x, int y) { return x > y ? x : y; }
  18.  
  19. int cmp(const void * arg1, const void * arg2) {
  20.   return *(const int *)arg1 - *(const int *)arg2;
  21. }
  22.  
  23. int rem_dups(int * xs, int n) {
  24.   int i,j;
  25.  
  26.   for ( j=0,i=1; i < n; ++i ) {
  27.     for ( j=j+1; j < n && xs[j] == xs[j-1]; ++j );
  28.     if ( j < n ) xs[i] = xs[j];
  29.     else break;
  30.   }
  31.   return i;
  32. }
  33.  
  34. void update(int p, int l, int r) {
  35.   if ( !st[p].upd ) return;
  36.   st[p].num = st[p].upd;
  37.   if ( l != r )
  38.     st[2*p].upd = st[2*p+1].upd = st[p].num;
  39.   st[p].upd = 0;
  40. }
  41.  
  42. void st_update(int p, int l, int r, int i, int j, int x) {
  43.   update(p, l, r);
  44.   if ( r < i || l > j )
  45.     return;
  46.   if ( l >= i && r <= j ) {
  47.     st[p].upd = x;
  48.     update(p, l, r);
  49.     return;
  50.   }
  51.   st_update(2*p, l, (l+r)/2, i, j, x);
  52.   st_update(2*p+1, (l+r)/2 + 1, r, i, j, x);
  53. }
  54.  
  55. int st_query(int p, int l, int r, int i, int j) {
  56.   int lt, rt;
  57.  
  58.   update(p, l, r);
  59.   if ( r < i || l > j )
  60.     return 0;
  61.   if ( l >= i && r <= j )
  62.     return st[p].num;
  63.   lt = st_query(2*p, l, (l+r)/2, i, j);
  64.   rt = st_query(2*p+1, (l+r)/2+1, r, i, j);
  65.   return max(lt, rt);
  66. }
  67.  
  68. int main() {
  69.   int i,n,q,t,x,ctr,acc;
  70.  
  71.   scanf("%d", &t);
  72.   while ( t-- ) {
  73.     memset(sn, 0, (MAX_P+1)*sizeof(*sn));
  74.     scanf("%d", &q);
  75.     for ( i=ctr=0; i < q; ++i ) {
  76.       scanf("%d %d", &qs[i].l, &qs[i].r);
  77.       xs[ctr++] = qs[i].l, xs[ctr++] = qs[i].r;
  78.     }
  79.     qsort(xs, 2*q, sizeof(*xs), cmp);
  80.     n = rem_dups(xs, 2*q);
  81.     for ( i=0; i < q; ++i ) {
  82.       int l = (int *)bsearch(&qs[i].l, xs, n, sizeof(*xs), cmp) - xs;
  83.       int r = (int *)bsearch(&qs[i].r, xs, n, sizeof(*xs), cmp) - xs;
  84.       st_update(1, 0,  2*MAX_P, l, r, i+1);
  85.     }
  86.     for ( i=acc=0; i < 2*q; ++i )
  87.       if ( (x = st_query(1, 0, 2*MAX_P, i, i)) )
  88.         if ( !sn[x] )
  89.           sn[x] = true, acc += 1;
  90.     printf("%d\n", acc);
  91.   }
  92.   return EXIT_SUCCESS;
  93. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top