Submission #716708

#	Time	Username	Problem	Language	Result	Execution time	Memory
716708		snpmrnhlol	Boat (APIO16_boat)	C++17	9 / 100	2069 ms	1128 KiB

boat

#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],dp3[1001],dp4[1001];;
int inv[250001];
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(){
    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++){
        for(j = 0;j < 1001;j++){
            dp2[j] = length[j];
            dp3[j] = length[j];
            dp4[j] = 1;
        }
        dp[i] = 1;
        for(j = i - 1;j >= 0;j--){
            if(segs[j] < segs[i]){
                dp[i] = (dp[i] + 1ll*dp[j]*dp2[segs[j]])%mod;
                dp3[segs[j]] = 1ll*dp3[segs[j]]*(length[segs[j]] - dp4[segs[j]])%mod*inv[dp4[segs[j]] + 1]%mod;
                dp4[segs[j]]++;
                if(dp4[segs[j]] <= length[segs[j]])dp2[segs[j]]+=dp3[segs[j]];
                dp2[segs[j]]%=mod;
            }
        }
        //cout<<dp[i]<<'\n';
    }
    ans = dp[cnt2 - 1] - 1;
    cout<<ans;
    return 0;
}

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