Submission #1352338

#TimeUsernameProblemLanguageResultExecution timeMemory
1352338sallyBoat (APIO16_boat)C++20
0 / 100
1 ms344 KiB
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
#define int long long
#define l first
#define r second
const int mod = 1e9+7;
const int MAXN = 500;
typedef pair<int,int> pii;
int N;
vector<pii> ran; // range
vector<int> bit(2*MAXN+1, 0), des, dp(2*MAXN+1, 0);
void update(int p, int val) {
    for(; p<=2*MAXN; p+=p&(-p)) {bit[p] = (bit[p] + val) % mod;}
    return;
}
int query(int p) {
    int res = 0;
    for(; p>0; p-=p&(-p)) res = (res + bit[p])%mod;
    return res;
}
signed main() {
    cin>>N;
    ran.resize(N);
    for(int i=0; i<N; i++) {
        int L, R;
        cin>>L>>R;
        ran[i].l = L;
        ran[i].r = R;
        des.push_back(L);
        des.push_back(R);
    }
    sort(des.begin(), des.end());
    des.resize(unique(des.begin(), des.end()) - des.begin());
    for(int i = 0; i<N; i++) {
        ran[i].l = lower_bound(des.begin(), des.end(), ran[i].l) - des.begin()+1;
        ran[i].r = lower_bound(des.begin(), des.end(), ran[i].r) - des.begin()+1;
        //cout<<ran[i].l<<' '<<ran[i].r<<'\n';
    }
    for(auto [L, R]: ran) {
        //cout<<L<<' '<<R<<'\n';
        vector<int> new_dp = dp;
        if(L == R) {
            new_dp[L] = (dp[L] + query(L-1) + 1) % mod; // +1 是加上dp[0]
            update(L, new_dp[L]);
        }
        else {
            for(int i = L; i<R; i++) {
                int span = (des[L] - des[L-1]);
                new_dp[i] = (dp[i] + (query(i-1) + 1)*span%mod) % mod;
            }
            new_dp[R] = (dp[R] + query(R-1) + 1)%mod;
            for(int i = L; i<=R; i++) update(i, new_dp[i] - dp[i]);
        }
        dp = new_dp;
        // for(int i=1; i<=2*N; i++) cout<<dp[i]<<' ';
        // cout<<'\n';
    }
    int ans = 0;
    for(int i=1; i<=dp.size()-1; i++) ans = (ans + dp[i])%mod;
    cout<<ans;
}

/*
0 1 2 3 4 5 6 7 8 9 10 = current maximum
new_dp[i] =( dp[i] + 前面的總和*i代表的範圍 % mod) % mod;
前面總和 => bit
dp[0] 恆 = 0
*/

/*
O(N*(2*N)*log2*N)
N<=500


0 1 2 3 4 5 6 7 8 9 10
1 1 1
1 1 
*/
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...