Submission #4023152

---

Source Code Expand

#include <bits/stdc++.h>
#define mset(a, b) memset(a, b, sizeof(a))
#define lc rt<<1
#define rc (rt<<1)|1
using namespace std;
typedef long long LL;
const int MAXN = 100005;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &AKNOI)
{
    T x=0, flag=1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') flag = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + ch - '0';
        ch = getchar();
    }
    AKNOI = flag*x;
}

int n, m, tr[MAXN];

struct Area
{
	int l, r, len;
	bool operator < (const Area &rhs) const {
		return len < rhs.len;
	}
}a[MAXN*3];

inline int lowbit(int x)
{
	return x & (-x);
}

inline void add(int x, int val)
{
	for(int i=x;i;i-=lowbit(i)){
		tr[i] += val;
	}
}

inline void update(int l, int r)
{
	add(l-1, -1);
	add(r, 1);
}

inline int query(int x)
{
	int ret = 0;
	for(int i=x;i<=m;i+=lowbit(i)){
		ret += tr[i];
	}
	return ret;
}

void init()
{
	read(n); read(m);
	for(int i=1;i<=n;++i){
		read(a[i].l); read(a[i].r);
		a[i].len = a[i].r - a[i].l + 1;
	}
	sort(a+1, a+n+1);
}

void solve()
{
	for(int i=1,j=1;i<=m;++i){
		while(j<=n && a[j].len == i){
			update(a[j].l, a[j].r);
			++j;
		}
		int ans = n-j+1;
		for(int k=i;k<=m;k+=i){
			ans += query(k);
		}
		printf("%d\n", ans);
	}
}

int main()
{
	init();
	solve();
	return 0;
}

Submission Info

Judge Result