oj.uz

Submission #716720

# Submission time Handle Problem Language Result Execution time Memory
716720 2023-03-30T23:23:18 Z snpmrnhlol Boat (APIO16_boat) C++17
0 / 100
 40 ms 1388 KB 
#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int segs[250001],dp[250001];
int length[1001];
int segl[1001];
int l[501],r[501];
int dp2[1001];
int inv[250001];
vector <int> v2[1001];
int p(int a,int b){
    int r = 1;
    while(b > 0){
        if(b%2 == 1)r = 1ll*r*a%mod;
        a = 1ll*a*a%mod;
        b/=2;
    }
    return r;
}
void precalc(){
    for(int i = 0;i <= 250000;i++){
        inv[i] = p(i,mod - 2);
    }
}
int main(){
    precalc();
    int n,i,cnt = 1,j,cnt2 = 0,ans = 0;
    cin>>n;
    for(i = 0;i < n;i++){
        cin>>l[i]>>r[i];
        segl[i*2] = l[i];
        segl[i*2+1] = r[i] + 1;
    }
    sort(segl,segl + 2*n);
    for(i = 1;i < 2*n;i++){
        if(segl[i] != segl[cnt - 1]){
            segl[cnt++] = segl[i];
        }
    }
    for(i = 0;i < n;i++){
        for(j = cnt - 1;j >= 0;j--){
            if(l[i] <= segl[j] && segl[j] <= r[i]){
                segs[cnt2++] = j;
                length[j] = segl[j + 1] - segl[j];
            }
        }
    }
    segs[cnt2++] = cnt;
    length[cnt] = 1;
    for(i = 0;i < cnt2;i++){
        dp[i] = 1;
        for(j = segs[i] - 1;j >= 0;j--){
            dp[i]+=dp2[j];
            //cout<<dp2[j]<<'\n';
        }
        ///update dp2[segs[i]]
        dp2[segs[i]] = 0;
        v2[segs[i]].push_back(dp[i]);
        int prod = length[segs[i]];
        for(j = v2[segs[i]].size() - 1;j >= 0;j--){
            dp2[segs[i]] = (dp2[segs[i]] + 1ll*v2[segs[i]][j]*prod)%mod;
            //cout<<prod<<' '<<(length[segs[i]] + v2[segs[i]].size() - j)<<' '<<v2[segs[i]].size() - j + 1<<'\n';
            prod = 1ll*prod*(length[segs[i]] + v2[segs[i]].size() - j)%mod;
            prod = 1ll*prod*inv[v2[segs[i]].size() - j + 1]%mod;
        }
        /*cout<<segs[i]<<' '<<dp2[segs[i]]<<'\n';*/
        //cout<<dp[i]<<'\n';
    }
    ans = dp[cnt2 - 1] - 1;
    cout<<ans;
    return 0;
}

Subtask #1
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 40 ms 1388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Incorrect 39 ms 1228 KB Output isn't correct
2 Halted 0 ms 0 KB -