Submission #5496562

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define debug(x) cerr << #x << ": " << x << ", "
#define debugln(x) cerr << #x << ": " << x << '\n'

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

using namespace std;
using ll = long long;
using P = pair<ll, ll>;

//constexpr ll mod = 998244353;
constexpr ll mod = 1e9+7;
const double PI = acos(-1.0);
mt19937_64 engine(chrono::steady_clock::now().time_since_epoch().count());

struct {
    int N;
    vector<long long> dat;

    void init(int n) {
      N = 1;
      while(N < n) N *= 2;
      dat.resize(2*N-1, 0);
    }

    // add [a, b) by x
    void add(int a, int b, long long x) {
      return add(a, b, x, 0, 0, N);
    }
    void add(int a, int b, ll x, int k, int l, int r) {
      if (r <= a || b <= l) return;
      if (a <= l && r <= b) {
        dat[k] += x;
        return;
      }
      int m = (l+r)/2;
      add(a, b, x, k*2+1, l, m);
      add(a, b, x, k*2+2, m, r);
    }

    // return k
    long long query(int k) {
      k += N-1;
      ll ret = dat[k];
      while(k > 0) {
        k = (k-1)/2;
        ret += dat[k];
      }
      return ret;
    }
} S;

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int n, m; cin >> n >> m;
  S.init(m);
  vector<P> vec;
  rep(i, n) {
    ll l, r; cin >> l >> r;
    vec.emplace_back(r-l, l*mod+r);
  }

  sort(vec.begin(), vec.end());
  int now = 1;
  rep(i, n) {
    P p = vec[i];
    ll l = vec[i].second/mod;
    ll r = vec[i].second%mod;
    ll range = vec[i].first+1;
    while(now <= range && now <= m) {
      ll ans = n-i;
      for(int j=now; j<=m; j+=now) {
        ans += S.query(j);
      }
      cout << ans << '\n';
      now++;
    }
    S.add(l, r+1, 1);
  }

  while(now <= m) {
    ll ans = 0;
    for(int j=now; j<=m; j+=now) {
      ans += S.query(j);
    }
    cout << ans << '\n';
    now++;
  }

}

Submission Info

Judge Result