Submission #1082192

---

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 long long 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;
  avl.resize(m+3);
  psm.resize(m+3);
  cin>>n>>m;
  in l,r;
  in tlm=1;
  while((tlm+1)*(tlm+1)<m)
    ++tlm;
  in nxt;
  in nr,nl;
  forn(zz,n){
    cin>>l>>r;
    for(in i=1;i<=tlm;++i){
      if(r/i!=(l-1)/i)
	++avl[i];
    }
    nxt=tlm+1;
    for(in hts=tlm+4;hts>=1;--hts){
      nl=(l-1)/hts+1;
      nr=r/hts;
      nl=max(nl,nxt);
      if(nl>nr)
	continue;
      ++psm[nl];
      --psm[nr+1];
      nxt=nr+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