Submission #1085135

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef int in;
typedef vector<in> VI;
typedef vector<VI> VVI;
VI avl;
VI psm;
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  in n,m;
  cin>>n>>m;
  avl.resize(m+3);
  psm.resize(m+3);
  in l,r;
  in S=1;
  while((S+1)*(S+1)<m)
    ++S;
  in nxt;
  in a,b;
  forn(zz,n){
    cin>>l>>r;
    for(in i=1;i<=S;++i){
      if(r/i!=(l-1)/i)
	++avl[i];
    }
    nxt=S+1;
    for(in k=S+4;k>=1;--k){
      a=(l-1)/k+1;
      b=r/k;
      a=max(a,nxt);
      if(a>b)
	continue;
      ++psm[a];
      --psm[b+1];
      nxt=b+1;
    }
  }
  for(in i=1;i<=m;++i){
    psm[i]+=psm[i-1];
    avl[i]+=psm[i];
    cout<<avl[i]<<"\n";
  }
  return 0;
}

Submission Info

Judge Result