Submission #1517624

---

Source Code Expand

#include <iostream>
#include <vector>
using namespace std;

class BIT{
	vector<int> bit;
	public:
	BIT(int siz) : bit(siz + 1,0){}
	void add(int i,int x){
		while(i < bit.size()){
			bit[i] += x;
			i += i & -i;
		}
	}
	int sum(int i){
		int s = 0;
		while(i){
			s += bit[i];
			i -= i & -i;
		}
		return s;
	}
};

int main(){
	int n,m;
	vector<int> vec[100001];
	cin >> n >> m;
	BIT bit(m);
	for(int i = 0;i < n;i++){
		int l,r;
		cin >> l >> r;
		vec[r - l].push_back(l);
	}
	int ans = n;
	for(int i = 0;i < m;i++){
		int add = 0;
		for(int j = i + 1;j <= m;j += i + 1) add += bit.sum(j);
		cout << ans + add << endl;
		for(int l : vec[i]){
			ans--;
			bit.add(l,1);
			bit.add(l + i + 1,-1);
		}
	}
	return 0;
}

Submission Info

Judge Result