Codeforce - Problem J New Protocol

http://codeforces.com/gym/100186/attachments/download/2093/statements.pdf

#include<cstdio>
#include<cstdlib>
#include<functional>
#include<cstring>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int n, m;
int tree[800001];
int base;
void init(){
 base = (1<<((int)(ceil(log2(m+2))))) - 1;
 //fprintf(stderr, "base = %d\n", base);
 for(int lx = 0;lx < 800001;lx++)
  tree[lx] = 0;
 return;
}
void addon(int a, int b){
 if(a > b)
  printf("%d\n", 1/0);
//fprintf(stderr, "add at %d %d\n",a , b);
 a++;
 b++;
 for(a += base-1, b+= base+1; a^b^1;a>>=1, b>>=1){
  if(~a&1) tree[a^1]++; // fprintf(stderr, "v %d\n", a^1);
  if(b&1) tree[b^1]++; //, fprintf(stderr,"v %d\n", b^1);
 }
 return;
}
int query(int p){
 int c = 0;
 for(int prc = p+base+1;prc;prc>>=1)
  c += tree[prc];
 return c;
}
int aaa[100004];
typedef pair<int,int> pii;
vector<pii> ccc[100001];
int main(){
 freopen("input.txt", "r", stdin);
 freopen("output.txt", "w", stdout);
 scanf("%d %d", &n, &m);
 for(int lx = 0;lx < n;lx++){
  scanf("%d", aaa+lx);
 }
 init();
 sort(aaa, aaa+n);
 int max_color = 0;
 for(int lx = 0;lx < n;lx++){
  int day = aaa[lx];
  if((lx == 0) or (aaa[lx-1] != aaa[lx])){
  //fprintf(stderr, "day = %d\n", day);
   for(int lt = 0;lt*day <= m;lt++){
    int left = lt*day, right = min((lt+1)*day-1, m);
    if(left <= m) ccc[lt].push_back(pii(left, right));
  //  fprintf( stderr, "addd00%d~%d\n", left, right);
     left = lt*day+1, right = min((lt+1)*day, m);
    if(left <= m) ccc[lt+1].push_back(pii(left, right));
  //  fprintf( stderr, "addd11%d~%d\n", left, right);
    max_color = max(max_color, lt+1);
   }
  }
 }
 for(int lx = 0;lx <= max_color;lx++){
  //fprintf(stdervis version %d\n", lx);
  if(ccc[lx].size() == 0) continue;
  sort(ccc[lx].begin(), ccc[lx].end());
  pii rec = ccc[lx][0];
  for(int ly = 1;ly < ccc[lx].size();ly++){
   if(ccc[lx][ly].first > rec.second){ // +----+ +----+
    addon(rec.first, rec.second);
    rec = ccc[lx][ly];
   }else
    rec.second = max(rec.second, ccc[lx][ly].second);
  }
  addon(rec.first, rec.second);
  //fprintf(stderr,"--------------\n");
 }
 int mm = 0;
 for(int lx = 0;lx <= m;lx++){
  mm = max(query(lx), mm);
  //fprintf(stderr,"cc%d = %d\n", lx, query(lx));
 }
 printf("%d\n", mm);
 return 0;
}