Submission #1238299

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238299		ProtonDecay314	Boat (APIO16_boat)	C++20	58 / 100	2096 ms	11044 KiB

boat

#include<bits/stdc++.h>
using namespace std;
#define double long double
typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<vvi> v3i;
typedef vector<v3i> v4i;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<double> vd;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
#define INF(dt) numeric_limits<dt>::max()
#define NINF(dt) numeric_limits<dt>::min()
#define pb push_back

const ll MOD = 1000000007ll;

// struct Tree {
//     Tree *lt, *rt;
//     ll l, r, v;
//     ll lazy;
    
//     Tree(ll a_l, ll a_r): lt(nullptr), rt(nullptr), l(a_l), r(a_r), v(0ll), lazy(0ll) {}
    
//     void combine() {
//         v = (lt->v + rt->v) % MOD;
//     }

//     void push() {
//         if(lazy == 0ll) return;
//         if(lt == nullptr) {
//             lazy = 0ll;
//             return;
//         }

//         lt->v = (lt->v + lazy) % MOD;
//         lt->lazy = (lt->lazy + lazy) % MOD;

//         rt->v = (rt->v + lazy) % MOD;
//         rt->lazy = (rt->lazy + lazy) % MOD;

//         lazy = 0ll;
//     }

//     void build(const vll& a) {
//         if(l == r) {
//             v = a[l];
//             return;
//         }
//         ll m = (l + r) >> 1ll;

//         lt = new Tree(l, m);
//         rt = new Tree(m + 1ll, r);
//         lt->build(a);
//         rt->build(a);
//         combine();
//     }

//     void upd(ll ql, ll qr, ll inc) {
//         if(ql > r || qr < l) return;

//         push();

//         if(ql == l && qr == r) {
//             v = (v + inc) % MOD;
//             lazy = (lazy + inc) % MOD;
            
//             return;
//         }

//         ll m = (l + r) >> 1ll;

//         lt->upd(ql, min(qr, m), inc);
//         rt->upd(max(ql, m + 1ll), qr, inc);

//         combine();
//     }

//     ll qry(ll ql, ll qr) {
//         if(ql > r || qr < l) return 0ll;

//         push();

//         if(ql == l && qr == r) return v;

//         ll m = (l + r) >> 1ll;

//         return (lt->qry(ql, min(qr, m)) + rt->qry(max(ql, m + 1ll), qr)) % MOD;
//     }
// };

ll fpw(ll b, ll pw, ll md) {
    if(pw == 0ll) return 1ll;
    ll bsqr = fpw((b * b) % md, pw >> 1ll, md);

    return (pw & 0b1ll ? (bsqr * b) % md : bsqr);
}

ll minv(ll n, ll md) {
    return fpw(n, md - 2ll, md);
}

ll conv(const vll& a, const vll& b) {
    ll n = a.size();
    assert((ll)(b.size()) == n);

    ll res = 0ll;
    for(ll i = 0ll; i < n; i++) {
        res = (res + a[i] * b[n - i - 1ll]) % MOD;
    }

    return res;
}

void printv(const vll& a) {
    for(ll v : a) cerr << v << " ";
    cerr << endl;
}

void printv(const vb& a) {
    for(bool v : a) cerr << v << " ";
    cerr << endl;
}

ll solve(ll n, const vpll& act_u, const vpll& deact_u, const vll& crit_vals) {
    vll a(n + 1ll, 1ll);

    ll act_u_ind = 0ll, deact_u_ind = 0ll;

    ll cvsz = crit_vals.size(), act_u_sz = act_u.size(), deact_u_sz = deact_u.size();

    vb act(n + 1ll, false);

    for(ll cvs_ind = 0ll; cvs_ind < cvsz - 1ll; cvs_ind++) {
        /*
        1. maintain an array of suffix increments
        2. process each activation in order
        3. process deactivations that match targ_k
        */
        ll cur_k = crit_vals[cvs_ind], targ_k = crit_vals[cvs_ind + 1ll];
        cerr << cur_k << " -> " << targ_k << endl;
        
        ll del_x = targ_k - cur_k;

        vll to_inc(n + 1ll, 0ll);
        /*
        binomial coeffs:
        dx + i C dx - 1

        (dx + i)! / (dx - 1)! (i + 1)! = (dx + i - 1)! / (dx - 1)! (i)! * (dx + i) / (i + 1)
        */

        while(act_u_ind < act_u_sz && act_u[act_u_ind].first == cur_k) {
            ll cur_ind = act_u[act_u_ind].second;
            act[cur_ind] = true;
            act_u_ind++;
        }

        while(deact_u_ind < deact_u_sz && deact_u[deact_u_ind].first < targ_k) {
            act[deact_u[deact_u_ind].second] = false;
            deact_u_ind++;
        }

        vll binc;
        vll vals;

        ll prev_conv = 0ll;
        for(ll i = 1ll; i <= n; i++) {
            if(!act[i]) continue;
            if((ll)(binc.size()) == 0ll) {
                binc.pb(del_x);
                vals.pb(a[i - 1ll]);
            } else {
                ll bincs = binc.size();
                binc.pb((((binc[bincs - 1ll] * (del_x + bincs)) % MOD) * minv(bincs + 1ll, MOD)) % MOD);
                vals.pb(a[i - 1ll]);
            }

            ll cur_conv = conv(binc, vals);
            to_inc[i] = (to_inc[i] + cur_conv - prev_conv) % MOD;
            prev_conv = cur_conv;
        }

        printv(binc);
        printv(vals);

        // step 2.5 (increment)
        for(ll i = 1ll; i <= n; i++) to_inc[i] = (to_inc[i - 1ll] + to_inc[i]) % MOD;

        for(ll i = 0ll; i <= n; i++) a[i] = (a[i] + to_inc[i]) % MOD;

        printv(a);
        printv(act);
    }

    return a[n];
}

int main() {
    ll n;
    cin >> n;

    vpll act_u;
    vpll deact_u;
    set<ll> crit_vals_set;
    for(ll i = 0ll; i < n; i++) {
        ll qa, qb;
        cin >> qa >> qb;
        qa--;
        
        act_u.pb({qa, i + 1ll});
        deact_u.pb({qb, i + 1ll});
        crit_vals_set.insert(qa);
        crit_vals_set.insert(qb);
    }

    vll crit_vals;
    for(ll v : crit_vals_set) crit_vals.pb(v);

    sort(act_u.begin(), act_u.end());
    sort(deact_u.begin(), deact_u.end());

    cout << solve(n, act_u, deact_u, crit_vals) - 1ll << endl;
}

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