Submission #1155253

#TimeUsernameProblemLanguageResultExecution timeMemory
1155253SangBoat (APIO16_boat)C++20
100 / 100
1312 ms25976 KiB
#include<bits/stdc++.h>
using namespace std;

#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; i++)
#define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; i--)
#define fi first
#define se second
#define pb push_back
#define ALL(a) (a).begin(), (a).end()
#define task "kbsiudthw"

typedef vector<int> vi;
typedef pair<int, int> ii;
typedef pair<int, ii> pii;

const int N = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int MOD = 1e9 + 7;

int n, L[505], R[505], dp[505][5005], pref[505][5005], dp2[5005][505], inv[505];

int Pow(int a, int b){
    if (b == 0) return 1;
    int t = Pow(a, b/2);
    t = (t * t)%MOD;
    if (b%2 == 0) return t;
    return (t * a)%MOD;
}

signed main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    if (fopen(task".inp", "r")){
        freopen(task".inp", "r", stdin);
        freopen(task".out", "w", stdout);
    }
    cin >> n ;
    FOR (i, 1, n) {
        cin >> L[i] >> R[i];
    }
    map<int, int> dd;
    vi vals;
    FOR (i, 1, n){
        int x = R[i];
        vals.pb(x);
        vals.pb(L[i]);
        if (x - 1) vals.pb(x-1);
        vals.pb(x+1);

    }
    sort(ALL(vals));
    vals.resize(unique(ALL(vals)) - vals.begin());
    int m = (int)vals.size();
    FOR (i, 1, n){
        L[i] = upper_bound(ALL(vals), L[i]) - vals.begin();
        R[i] = upper_bound(ALL(vals), R[i]) - vals.begin();
    }
    FOR (i, 1, 504) inv[i] = Pow(i, MOD - 2);
    dp[0][m + 1] = 1;
    FOR (i, 1, n){
        FORD(j, i-1, 0){
            FOR (k, L[i], R[i] - 1){
                int cnt = vals[k]-vals[k-1];
                dp[i][k] = (dp[i][k] + (pref[j][k-1] * cnt)%MOD)%MOD;
                if (k >= R[j]){
                    dp[i][k] = (dp[i][k] + (dp[j][m+1] * (cnt - (k == R[j])))%MOD)%MOD;
                }
            }
            dp[i][m+1] = (dp[i][m+1] + pref[j][R[i]-1])%MOD;
            if (R[i] > R[j]){
                dp[i][m+1] = (dp[i][m+1] + dp[j][m+1])%MOD;
            }
        }
        FOR (k, L[i], R[i] - 1){
            int cnt = vals[k] - vals[k-1];
            int ans = 0;
            FORD(j, min(n, cnt), 2){
                int t = inv[j] * (cnt - j + 1)%MOD;
                ans = (ans + dp2[k][j-1] * t%MOD)%MOD;
                dp2[k][j] = (dp2[k][j] + dp2[k][j-1] * t%MOD)%MOD;
            }
            dp2[k][1] = (dp2[k][1] + dp[i][k])%MOD;
            dp[i][k] = (dp[i][k] + ans)%MOD;
        }
        FOR (j, 1, m) pref[i][j] = (pref[i][j-1] + dp[i][j])%MOD;
    }
    /*
    3
    1 5
    5 10
    5 15
    */
//    FOR (i, 1, n){
//        FOR (j, 1, m + 1) cout << dp[i][j] << ' ';
//        cout << '\n';
//    }
    int ans = 0;
    FOR (i, 1, n){
        ans = (ans + dp[i][m+1])%MOD;
        FOR (k, L[i], R[i]-1) ans = (ans + dp[i][k])%MOD;
    }
    cout << ans;


    return 0;
}

Compilation message (stderr)

boat.cpp: In function 'int main()':
boat.cpp:35:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         freopen(task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
boat.cpp:36:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |         freopen(task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...