Submission #1833213

---

Source Code Expand

import std.stdio, std.string, std.conv, std.algorithm, std.numeric;
import std.range, std.array, std.math, std.typecons, std.container, core.bitop;

alias Seg = Tuple!(int, "l", int, "r");

void main() {
    int n, m;
    scan(n, m);

    auto ft = fenwickTree(m + 1);
    auto sgs = new Seg[](n);

    foreach (i ; 0 .. n) {
        int li, ri;
        scan(li, ri);
        sgs[i] = Seg(li, ri);
    }

    sgs.sort!"a.r - a.l < b.r - b.l"();

    debug {
        writeln(sgs);
    }

    writeln(n);

    foreach (d ; 2 .. m + 1) {
        while (!sgs.empty && sgs[0].r - sgs[0].l + 1 < d) {
            ft.add(sgs[0].l, 1);
            ft.add(sgs[0].r + 1, -1);
            sgs.popFront();
        }

        int ans;

        for (int i = d; i <= m; i += d) {
            ans += ft.psum(i);
        }

        ans += sgs.length.to!int;

        writeln(ans);
    }
}

struct fenwickTree {
    private {
        int N;
        int[] data;
    }

    this (int n) {
        N = n;
        data = new int[](N + 1);
    }

    void add(int i, int x) {
        while (i <= N) {
            data[i] += x;
            i += i & (-i);
        }
    }

    int psum(int r) {
        return r > 0 ? psum(r - (r & (-r))) + data[r] : 0;
    }
}

void scan(T...)(ref T args) {
    string[] line = readln.split;
    foreach (ref arg; args) {
        arg = line.front.to!(typeof(arg));
        line.popFront();
    }
    assert(line.empty);
}


void fillAll(R, T)(ref R arr, T value) {
    static if (is(typeof(arr[] = value))) {
        arr[] = value;
    }
    else {
        foreach (ref e; arr) {
            fillAll(e, value);
        }
    }
}

Submission Info

Judge Result