Submission #62642

---

Source Code Expand

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

typedef pair<int, int> Pair;
const int kMod = 1000000007;

struct Train
{
    int s, t;

    bool operator<(const Train& other) const
    {
        if (s != other.s) return s < other.s;
        return t < other.t;
    }
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<Train> trains(m);
    for (int i = 0; i < m; i++) {
        cin >> trains[i].s >> trains[i].t;
        --trains[i].s, --trains[i].t;
    }

    sort(trains.begin(), trains.end());

    map<Pair, int> counts;
    counts[Pair(0, 0)] = 1;
    for (int i = 0; i < m; i++) {
        int s = trains[i].s;
        int t = trains[i].t + 1;

        map<Pair, int> next(counts);
        for (map<Pair, int>::reverse_iterator p = counts.rbegin();
             p != counts.rend(); ++p) {
            int u = p->first.first, v = p->first.second;
            if (t <= u) {
                next[Pair(u, v)] = (next[Pair(u, v)] + counts[Pair(u, v)]) % kMod;
                continue;
            }
            if (s > u) continue;
            if (t <= v) {
                next[Pair(t, v)] = (next[Pair(t, v)] + counts[Pair(u, v)]) % kMod;
                continue;
            }
            if (s <= u) {
                next[Pair(v, t)] = (next[Pair(v, t)] + counts[Pair(u, v)]) % kMod;
                continue;
            }
        }
        counts.swap(next);
    }

    cout << counts[Pair(n, n)] << endl;
    return 0;
}

Submission Info

Judge Result