Submission #1150052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150052		vladilius	Boat (APIO16_boat)	C++20	36 / 100	2094 ms	2304 KiB

boat

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define pb push_back
#define ff first
#define ss second
const int mod = 1e9 + 7;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    auto bin_pow = [&](int x, int y){
        int out = x, pr = x; y--;
        while (y > 0){
            if (y & 1){
                out = (1LL * out * pr) % mod;
            }
            pr = (1LL * pr * pr) % mod;
            y >>= 1;
        }
        return out;
    };
    
    auto inv = [&](int x){
        if (x < 0) x += mod;
        return bin_pow(x, mod - 2);
    };
    
    int n; cin>>n;
    vector<int> pw(n + 3, 1), P[n + 3], T[n + 3];
    for (int i = 1; i <= n + 2; i++){
        T[i] = {0, inv(i)};
    }
    
    vector<int> f(n + 3), d;
    auto mult = [&](vector<int>& a){
        for (int i = 0; i < n + 3; i++) f[i] = 0;
        for (int i = 0; i < a.size(); i++){
            for (int j = 0; j < 2; j++){
                f[i + j] = (f[i + j] + 1LL * a[i] * d[j]) % mod;
            }
        }
    };
    
    for (int x = 1; x <= n + 2; x++){
        for (int j = 1; j <= n + 2; j++){
            if (j != x){
                int v = (-1LL * x * inv(j - x)) % mod + mod;
                d = {v, inv(j - x)};
                mult(T[j]);
                T[j].resize(T[j].size() + 1);
                for (int t = 0; t < T[j].size(); t++){
                    T[j][t] = f[t];
                }
            }
        }
        P[x - 1].resize(x + 1);
        int X = 0;
        for (int i = 1; i <= x; i++){
            X = (X + pw[i]) % mod;
            for (int j = 0; j < T[i].size(); j++){
                P[x - 1][j] = (P[x - 1][j] + 1LL * T[i][j] * X) % mod;
            }
        }
        for (int j = 1; j <= n + 2; j++){
            pw[j] = (1LL * pw[j] * j) % mod;
        }
    }
    set<pair<int, pair<int, vector<int>>>> st;
    st.insert({1, {1e9, {0}}});
    
    auto split = [&](int x){
        auto it = st.lower_bound({x + 1, {}});
        if (it != st.begin()){
            it--;
            if ((*it).ss.ff != x){
                int l = (*it).ff, r = (*it).ss.ff;
                vector<int> f = (*it).ss.ss;
                st.erase(it);
                st.insert({l, {x, f}});
                st.insert({x + 1, {r, f}});
            }
        }
    };
    
    auto F = [&](int i, int j){
        int out = 0, X = 1;
        for (int t = 0; t < P[i].size(); t++){
            out = (out + 1LL * P[i][t] * X) % mod;
            X = (1LL * X * j) % mod;
        }
        return out;
    };
    
    for (int tt = 1; tt <= n; tt++){
        int l, r; cin>>l>>r;

        split(l - 1); split(r);

        int X = 0;
        auto it = st.begin();
        while ((*it).ff < l){
            int a = (*it).ff, b = (*it).ss.ff;
            vector<int> f = (*it).ss.ss;
            for (int i = 0; i < f.size(); i++){
                X = (X + 1LL * f[i] * (F(i, b) - F(i, a - 1))) % mod;
            }
            it++;
        }
        while (it != st.end() && (*it).ff <= r){
            int a = (*it).ff, b = (*it).ss.ff;
            vector<int> f = (*it).ss.ss, t((int) f.size() + 2); t[0] = (X + 1) % mod;
            for (int i = 0; i < f.size(); i++){
                for (int s = 0; s < P[i].size(); s++){
                    t[s] = (t[s] + 1LL * f[i] * P[i][s]) % mod;
                }
                t[0] = (t[0] - 1LL * f[i] * F(i, a - 1)) % mod;
                X = (X + 1LL * f[i] * (F(i, b) - F(i, a - 1))) % mod;
            }
            
            while (t.size() > 1 && !t.back()) t.pop_back();
            
            st.erase(it);
            st.insert({a, {b, t}});
            it = st.find({a, {b, t}}); it++;
        }
    }
    auto it = st.begin();
    int out = 0;
    while (it != st.end()){
        int a = (*it).ff, b = (*it).ss.ff;
        vector<int> f = (*it).ss.ss;
        for (int i = 0; i < f.size(); i++){
            out = (out + 1LL * f[i] * (F(i, b) - F(i, a - 1))) % mod;
        }
        it++;
    }
    if (out < 0) out += mod;
    cout<<out<<"\n";
}

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