Submission #1421485

---

Source Code Expand

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define lc (o << 1)
#define rc (o << 1 | 1)
#define mid ((l+r) >> 1)
using namespace std;
typedef pair<int,int> P;

const int maxn = 100009;
int T[maxn<<2], lazy[maxn<<2];
vector<P> q[maxn];
int n, m, cnt = 0, a, b, ans;

inline int read(){
	char ch = getchar(); int x = 0;
	while (ch < '0' || '9' < ch) ch = getchar(); 
	while ('0' <= ch && ch <= '9') { x = x*10+ch-'0'; ch = getchar(); }
	return x;
}

void pushdown(int o, int l, int r){
	if (!lazy[o]) return;
	T[lc] += lazy[o]*(mid-l+1);
	lazy[lc] += lazy[o];
	T[rc] += lazy[o]*(r-mid);
	lazy[rc] += lazy[o];
	lazy[o] = 0;
}

int query(int o, int l, int r, int x){
	if (l == r) return T[o];
	pushdown(o, l, r);
	if (x <= mid) return query(lc, l, mid, x);
	return query(rc, mid+1, r, x);
}

void update(int o, int l, int r, int x, int y){
	if (l == x && y == r){
		T[o] += r-l+1;
		lazy[o]++;
		return;
	}
	pushdown(o, l, r);
	if (x <= mid) update(lc, l, mid, x, min(y, mid));
	if (mid+1 <= y) update(rc, mid+1, r, max(x, mid+1), y);
}

int main(){
	n = read(); m = read();
	for (int i=1; i<=n; i++){
		a = read(); b = read();
		q[b-a+1].push_back(make_pair(a, b));
	}
	for (int i=1; i<=m; i++){
		ans = n-cnt;
		for (int j=i; j<=m; j+=i)
			ans += query(1, 1, m, j);
		printf("%d\n", ans);
		for (int j=q[i].size()-1; j>=0; j--){
			P t = q[i][j];  cnt++;
			update(1, 1, m, t.first, t.second);
		}
	}
	return 0;
}

Submission Info

Judge Result