Submission #1215915

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215915		zhenja	Boat (APIO16_boat)	C++20	100 / 100	1808 ms	8700 KiB

boat

#include <iostream>
#include<string>
#include<cmath>
#include<map>
#include<iomanip>
#include<algorithm>
#include<vector>
#include<set>
#include<cstdio>
#include<stack>
#include<ctime>
#include<queue>
#include<deque>
#include<bitset>
#include<random>
#include<fstream>
#include<unordered_map>
#include<unordered_set>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using uint = unsigned int;
using dbl = double;

# define all(x) x.begin(), x.end()
# define rall(x) x.rbegin(), x.rend()

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}
ll lcm(ll a, ll b) {
    return a / gcd(a, b) * b;
}
ll bpow(ll a, ll n) {
    return n == 0 ? 1 : n % 2 ? bpow(a, n - 1) * a : bpow(a * a, n / 2);
}
ll bpowm(ll a, ll n, ll m) {
    return n == 0 ? 1 : n % 2 ? bpowm(a, n - 1, m) * a % m : bpowm(a * a % m, n / 2, m);
}
mt19937_64 mt(time(0));
const int N = 1e3 + 2, M = 5e5 + 2, inf = 1e9 + 10, mod = 1e9 + 7, mod2 = 998244353, P = 257, htm = 30000001;
const ll llinf = 1e18 + 100;
int add(int a, int b) {
    return a + b - mod * (a + b >= mod);
}
ll inv(ll x) {
    return bpowm(x, mod - 2, mod);
}
struct fenwick {
    int t[M];
    fenwick() {
        fill(t, t + M, 0);
    }
    void upd(int i, int x) {
        for (++i; i < M; i += (i & -i)) t[i] = add(t[i], x);
    }
    int get(int r) {
        int ans = 0;
        for (; r; r -= (r & -r)) ans = add(ans, t[r]);
        return ans;
    }
};
int n, m = 1;
pair<int, int> a[N];
int b[M];
vector<int> pos[N];
int dp[N][N][2];

void solve() {
    cin >> n;
    vector<int> vals;
    for (int i = 0; i < n; ++i) {
        cin >> a[i].first >> a[i].second;
        ++a[i].second;
        vals.push_back(a[i].first);
        vals.push_back(a[i].second);
    }
    sort(all(vals));
    vals.erase(unique(all(vals)), vals.end());
    for (int i = 0; i < n; ++i) {
        int l = lower_bound(all(vals), a[i].first) - vals.begin();
        int r = lower_bound(all(vals), a[i].second) - vals.begin() - 1;
        for (; r >= l; --r) {
            b[m] = r;
            pos[r].push_back(m);
            ++m;
        }
    }
    fenwick t;
    t.upd(0, 1);
    for (int val = 0; val < vals.size() - 1; ++val) {
        int k = pos[val].size();
        for (int i = 0; i < k; ++i) {
            for (int j = 0; j <= k; ++j) {
                dp[i][j][0] = 0;
                dp[i][j][1] = 0;
            }
        }
        for (int i = 0; i < k; ++i) {
            dp[i][1][1] = t.get(pos[val][i]);
            if (i + 1 == k) break;
            for (int j = 0; j <= i + 1; ++j) {
                dp[i + 1][j][0] = add(dp[i + 1][j][0], add(dp[i][j][0], dp[i][j][1]));
                dp[i + 1][j + 1][1] = add(dp[i + 1][j + 1][1], add(dp[i][j][0], dp[i][j][1]));
            }
        }
        int len = vals[val + 1] - vals[val];
        ll C = len;
        for (int c = 1; c <= min(k, len); ++c) {
            for (int i = 0; i < k; ++i) {
                t.upd(pos[val][i], dp[i][c][1] * C % mod);
            }
            C *= (len - c);
            C %= mod;
            C *= inv(c + 1);
            C %= mod;
        }
    }
    cout << (t.get(M - 1) - 1 + mod) % mod;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    //freopen("coloring.in", "r", stdin);
    //freopen("coloring.out", "w", stdout);

    //ld time1 = clock();

    int tt = 1;
    //cin >> tt;
    while (tt--) {
        solve();
        cout << '\n';
        cout.flush();
    }

    //ld time2 = clock();
    //cerr << "\n\nTIME: " << (time2 - time1) / CLOCKS_PER_SEC;
    return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 27 / 27
• Subtask 4: 42 / 42