제출 #716723

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
716723		snpmrnhlol	Boat (APIO16_boat)	C++11	100 / 100	942 ms	4660 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];
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];
            dp[i]%=mod;
        }
        ///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;
            prod = 1ll*prod*(length[segs[i]] + v2[segs[i]].size() - j)%mod;
            prod = 1ll*prod*inv[v2[segs[i]].size() - j + 1]%mod;
        }
    }
    ans = (dp[cnt2 - 1] + mod - 1)%mod;
    cout<<ans;
    return 0;
}

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