Submission #1271847

#	Time	Username	Problem	Language	Result	Execution time	Memory
1271847		ZeroCool	Boat (APIO16_boat)	C++20	100 / 100	1126 ms	4420 KiB

boat

#include <bits/stdc++.h>
using namespace std;;
#define ll long long
#define ar array
#define ld double
#define int long long
#define all(v) v.begin(), v.end()

//  #pragma GCC optimize("O3,Ofast,unroll-loops ")

const int N = 3010;
const int M = 20;
const int LOG = 20;
const int INF = 1e17;	
int MOD = 1e9 + 7;
const ld EPS = 1e-12;

template<typename T>
inline void chmin(T &x,T y){x = min(x, y);}
template<typename T>
inline void chmax(T &x,T y){x = max(x, y);}
inline void mm(int &x){x = (x % MOD + MOD) % MOD;};

int W(int l1,int r1,int l2,int r2){
    int a = max(l1, l2 + 1);
    int b = min(r1, r2);
    int c = max(r2 + 1, l1);
    int x = r2 - l2 + 1;
    int u = max(0ll, b - a + 1) * (a + b - 2 * l2) / 2;
    int v = max(0ll, r1 -  c + 1) * x;
    mm(u);
    mm(v); 
    return (u + v) % MOD;
}

int inv[N];

int P(int a,int b){
    int ans = 1;
    while(b){
        if(b % 2)mm(ans *= a);
        b /= 2;
        mm(a *= a);
    }
    return ans;
}

void orz(){
    inv[0] = 1;
    for(int i = 1;i < N;i++)inv[i] = P(i, MOD - 2);
    int n;
    cin>>n;
    int L[n + 1], R[n + 1];
    // cout<<P(2, 5)<<'\n';
    for(int i = 1;i <= n;i++)cin>>L[i]>>R[i];
    vector<int> v;
    for(int i = 1;i <= n;i++)v.push_back(L[i]), v.push_back(R[i] + 1);
    sort(all(v));
    v.erase(unique(all(v)), v.end());
    vector<ar<int,2>> S = {{0, 0}};
    for(int i = 0;i + 1 < v.size();i++)S.push_back({v[i], v[i + 1] - 1});
    int m = S.size();
    int dp[n + 1][m];
    memset(dp, 0, sizeof dp);
    for(int i = 0;i < m;i++)dp[0][i] = 1;
    for(int i = 1;i <= n;i++){
        dp[i][0] = 1;
        for(int j = 1;j < m;j++){
            dp[i][j] = dp[i][j - 1];
            auto [l, r] = S[j];
            int cnt = 0, mult = 1;
            for(int k = i;k;k--){
                if(L[k] <= l && r <= R[k]){
                    cnt++;
                    mm(mult *= ((r - l + cnt) * inv[cnt]) % MOD);
                    mm(dp[i][j] += (dp[k - 1][j - 1] * mult) % MOD);
                }
            }
        }
    }
    int ans = dp[n][m - 1];
    mm(ans -= 1);
    cout<<ans;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t = 1;
    //  cin>>t;
    while (t--)orz();
}   

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