AtCoder Grand Contest 015: E - Mr.Aoki Incubator

,

http://agc015.contest.atcoder.jp/tasks/agc015_e

反省

直前に同様に区間と被覆に落とす問題を解いたのに思い付けなかった。 座標ばかりに注目して速度の区間というのが出てこなかった。 頭がほしい。

solution

editorialを見て。 ただしDPを$O(N^2)$から$O(N)$にする部分はbinary indexed treeとかsegment treeとかを使った方が楽。

implementation

#include <algorithm>
#include <cstdio>
#include <map>
#include <numeric>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
#define repeat_reverse(i, n) for (int i = (n)-1; (i) >= 0; --(i))
#define whole(f, x, ...) ([&](decltype((x)) whole) { return (f)(begin(whole), end(whole), ## __VA_ARGS__); })(x)
using namespace std;

template <typename Monoid>
struct binary_indexed_tree { // on monoid
    typedef typename Monoid::underlying_type underlying_type;
    vector<underlying_type> data;
    Monoid mon;
    binary_indexed_tree(size_t n, Monoid const & a_mon = Monoid()) : mon(a_mon) {
        data.resize(n, mon.unit());
    }
    void point_append(size_t i, underlying_type z) { // data[i] += z
        for (size_t j = i + 1; j <= data.size(); j += j & -j) data[j - 1] = mon.append(data[j - 1], z);
    }
    underlying_type initial_range_concat(size_t i) { // sum [0, i)
        underlying_type acc = mon.unit();
        for (size_t j = i; 0 < j; j -= j & -j) acc = mon.append(data[j - 1], acc);
        return acc;
    }
    underlying_type range_concat(size_t l, size_t r) {
        return mon.append(initial_range_concat(r), mon.invert(initial_range_concat(l)));
    }
};
template <int mod>
struct modplus_t {
    typedef int underlying_type;
    int unit() const { return 0; }
    int append(int a, int b) const { int c = a + b; return c < mod ? c : c - mod; }
    int invert(int a) const { return a ? mod - a : 0; }
};

template <typename T>
map<T,int> coordinate_compression_map(vector<T> const & xs) {
    int n = xs.size();
    vector<int> ys(n);
    whole(iota, ys, 0);
    whole(sort, ys, [&](int i, int j) { return xs[i] < xs[j]; });
    map<T,int> f;
    for (int i : ys) {
        if (not f.count(xs[i])) { // make unique
            int j = f.size();
            f[xs[i]] = j; // f[xs[i]] has a side effect, increasing the f.size()
        }
    }
    return f;
}
template <typename T>
vector<int> apply_compression(map<T,int> const & f, vector<T> const & xs) {
    int n = xs.size();
    vector<int> ys(n);
    repeat (i,n) ys[i] = f.at(xs[i]);
    return ys;
}
void sort_with_pair(int n, vector<int> & a, vector<int> & b) {
    vector<pair<int, int> > c(n);
    repeat (i, n) {
        c[i] = { a[i], b[i] };
    }
    whole(sort, c);
    repeat (i, n) {
        tie(a[i], b[i]) = c[i];
    }
}

constexpr int mod = 1e9+7;
int main() {
    // input
    int n; scanf("%d", &n);
    vector<int> x(n), v(n); repeat (i, n) scanf("%d%d", &x[i], &v[i]);
    x = apply_compression(coordinate_compression_map(x), x);
    v = apply_compression(coordinate_compression_map(v), v);
    // solve
    sort_with_pair(n, x, v);
    vector<int> l(n); // [l, r)
    l[n - 1] = v[n - 1];
    repeat_reverse (i, n - 1) {
        l[i] = min(l[i + 1], v[i]);
    }
    vector<int> r(n);
    r[0] = v[0] + 1;
    repeat (i, n - 1) {
        r[i + 1] = max(r[i], v[i + 1] + 1);
    }
    binary_indexed_tree<modplus_t<mod> > dp(n + 1);
    dp.point_append(0, 1);
    repeat (i, n) {
        dp.point_append(r[i], dp.range_concat(l[i], r[i] + 1));
    }
    // output
    printf("%d\n", dp.range_concat(n, n + 1));
    return 0;
}