Submission #1179491

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

const int N = 200000;
int tr[N], n, m;
void add(int t, int d) { for (; t; t -= t & (-t)) tr[t] += d;}
int sum(int t) { int d = 0; for (; t <= m; t += t & (-t)) d += tr[t]; return d;}
vector <int> AD[N], ASa[N], ASb[N], ASc[N];
int ans[N];
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i)
    {
        int l, r;
        cin >> l >> r;
        AD[l].push_back(r);
    }
    for (int i = 1; i <= m; ++ i)
        for (int j = i; j <= m; j += i)
            ASa[j - i].push_back(j), ASb[j - i].push_back(-1), ASc[j - i].push_back(i),
            ASa[j].push_back(j), ASb[j].push_back(1), ASc[j].push_back(i);

    for (int i = 1; i <= m; ++ i)
    {
        for (int j = 0; j < AD[i].size(); ++ j) add(AD[i][j], 1);
        for (int j = 0; j < ASa[i].size(); ++ j)
            ans[ASc[i][j]] += ASb[i][j] * sum(ASa[i][j]);
    }
    for (int i = 1; i <= m; ++ i)
        cout << ans[i] << "\n"; 
}

Submission Info

Judge Result