fork download 
  1. #include "elephants.h"
  2. #include <math.h>
  3.  
  4. #define MAXN 150004
  5. #define MAXS 390
  6.  
  7. static int L,G,SZ,update_count;
  8. static int X[MAXN],P[MAXN];
  9.  
  10. static struct GROUP{
  11.     int arr[MAXS*2],count[MAXS*2],last[MAXS*2],size;
  12.     void set(){
  13.         int i,k=size;
  14.         for (i=size;i;i--){
  15.             while (k > i && arr[k-1]-arr[i] > L) k--;
  16.             if (arr[size]-arr[i] <= L) count[i] = 1, last[i] = arr[i]+L;
  17.             else count[i] = count[k]+1, last[i] = last[k];
  18.         }
  19.     }
  20. } groups[MAXS];
  21.  
  22. void all_set()
  23. {
  24.     int N=0,i,j;
  25.     for (i=1;i<=G;i++){
  26.         for (j=1;j<=groups[i].size;j++) X[++N] = groups[i].arr[j];
  27.         groups[i].size = 0;
  28.     }
  29.     G = 1;
  30.     for (i=1;i<=N;i++){
  31.         if (groups[G].size == SZ) G++;
  32.         groups[G].arr[++groups[G].size] = X[i];
  33.     }
  34.     for (i=1;i<=G;i++) groups[i].set();
  35.     update_count = 0;
  36. }
  37.  
  38. int get_answer()
  39. {
  40.     int i,ans=groups[1].count[1],last=groups[1].last[1];
  41.     int s,e,m,t;
  42.     for (i=2;i<=G;i++){
  43.         if (groups[i].arr[groups[i].size] <= last) continue;
  44.         s = 1, e = groups[i].size;
  45.         while (s <= e){
  46.             m = (s+e)>>1;
  47.             if (groups[i].arr[m] > last) e = m-1, t = m;
  48.             else s = m+1;
  49.         }
  50.         ans += groups[i].count[t];
  51.         last = groups[i].last[t];
  52.     }
  53.     return ans;
  54. }
  55.  
  56. int del(int p)
  57. {
  58.     int i,t;
  59.     for (t=1;t<G;t++) if (groups[t].arr[1] <= p && groups[t+1].arr[1] > p) break;
  60.     for (i=1;i<=groups[t].size;i++){
  61.         if (groups[t].arr[i] == p){
  62.             for (;i<groups[t].size;i++) groups[t].arr[i] = groups[t].arr[i+1];
  63.             groups[t].size--;
  64.             break;
  65.         }
  66.     }
  67.     groups[t].set();
  68.     return groups[t].size;
  69. }
  70.  
  71. void add(int p)
  72. {
  73.     int i,t,x;
  74.     for (t=1;t<G;t++) if (groups[t].arr[groups[t].size] > p) break;
  75.     for (x=1;x<=groups[t].size;x++) if (groups[t].arr[x] > p) break;
  76.     for (i=groups[t].size;i>=x;i--) groups[t].arr[i+1] = groups[t].arr[i];
  77.     groups[t].arr[x] = p;
  78.     groups[t].size++;
  79.     groups[t].set();
  80. }
  81.  
  82. void init(int N, int l, int x[])
  83. {
  84.     int i;
  85.     L = l;
  86.     SZ = (int)sqrt((double)N); G = 1;
  87.     for (i=0;i<N;i++){
  88.         P[i] = x[i];
  89.         if (groups[G].size == SZ) G++; /* TODO: modify */
  90.         groups[G].arr[++groups[G].size] = x[i];
  91.     }
  92.     for (i=1;i<=G;i++) groups[i].set();
  93. }
  94.  
  95. int update(int i, int y)
  96. {
  97.     if (++update_count == SZ) all_set();
  98.     if (!del(P[i])) all_set();
  99.     add(P[i]=y);
  100.     return get_answer();
  101. }
  102.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/SVFZ8z
language:
C++ (gcc 8.3)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!