Submission #947832

#	Time	Username	Problem	Language	Result	Execution time	Memory
947832		RGBB	Boat (APIO16_boat)	C++14	100 / 100	1421 ms	6168 KiB

boat

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <cstdint>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pll;
typedef pair<double, double> pd;
typedef pair<ld, ld> pld;
typedef tuple<int, int, int> ti;
typedef tuple<ll, ll, ll> tll;
typedef tuple<double, double, double> td;
typedef complex<double> cd;
typedef tree<pair<int, int>, null_type, less<pair<int, int>>, rb_tree_tag, tree_order_statistics_node_update> bbst;


mt19937 g1;
int get_random_int(int a, int b) {
    return uniform_int_distribution<int>(a, b)(g1);
}

//const ll MOD = 100000000105583;
int MOD = 1e9 + 7;
//int MOD = 998244353;
struct Mint {
    int v;
    Mint() {v = 0;}
    Mint(int nv) {v = nv;}
    Mint(const Mint &a) {v = a.v;}
    Mint pow(int a) {
        long long ret = 1;
        long long base = v;
        if(a < 0) {
            a = -a;
            base = Mint(v).inv().v;
        }
        while(a > 0) {
            if(a & 1) ret = (ret * base) % MOD;
            base = (base * base) % MOD;
            a >>= 1;
        }
        return Mint((int)ret);
    }
    Mint inv() {return this->pow(MOD - 2);}
    Mint operator + (int a) const {return Mint((v + a) % MOD);}
    Mint operator + (const Mint &a) const {return Mint((v + a.v) % MOD);}
    Mint& operator += (int a) {
        v = (v + a) % MOD;
        return *this;
    }
    Mint& operator += (const Mint &a) {
        v = (v + a.v) % MOD;
        return *this;
    }
    Mint operator - (int a) const {return Mint((v - a + MOD) % MOD);}
    Mint operator - (const Mint &a) const {return Mint((v - a.v + MOD) % MOD);}
    Mint& operator -= (int a) {
        v = (v - a + MOD) % MOD;
        return *this;
    }
    Mint& operator -= (const Mint &a) {
        v = (v - a.v + MOD) % MOD;
        return *this;
    }
    Mint operator * (int a) const {return Mint(((long long)v * a) % MOD);}
    Mint operator * (const Mint &a) const {return Mint(((long long)v * a.v) % MOD);}
    Mint& operator *= (int a) {
        v = ((long long)v * a) % MOD;
        return *this;
    }
    Mint& operator *= (const Mint &a) {
        v = ((long long)v * a.v) % MOD;
        return *this;
    }
    Mint operator / (int a) const {return Mint(v) * Mint(a).inv();}
    Mint operator / (const Mint a) const {return Mint(v) * Mint(a).inv();}
    Mint& operator /= (int a) {
        v = ((long long)v * Mint(a).inv().v) % MOD;
        return *this;
    }
    Mint& operator /= (const Mint &a) {
        v = ((long long)v * Mint(a).inv().v) % MOD;
        return *this;
    }
    Mint& operator = (int a) {
        v = a;
        v %= MOD;
        if(v < 0) v += MOD;
        return *this;
    }
    bool operator == (int a) const {return v == a;}
    bool operator == (const Mint &a) const {return v == a.v;}
    bool operator != (int a) const {return v != a;}
    bool operator != (const Mint &a) const {return v != a.v;}
    friend ostream& operator << (ostream &os, const Mint &a) {
        os << a.v;
        return os;
    }
};

const int MAX = 500;

Mint qinv[2 * MAX];
void calcQinv() {
    for(int i = 1; i < 2 * MAX; i++) qinv[i] = Mint(i).inv();
}

struct prefixBinom {
    int degree, size;
    Mint coeff, sum; // Note that sum is without coeff
    /*
    Degree 0 implies only coeff throughout
    */
    prefixBinom(): degree{0}, size{0}, coeff{Mint(0)}, sum{Mint(0)} {}
    prefixBinom(int s, Mint c): degree{0}, size{s}, coeff{c}, sum{Mint(s)} {}
    void incDegree() {
        sum *= (degree + size + 1);
        sum *= qinv[degree + 2];
        degree++;
    }
    Mint calcVal() {
        return coeff * sum;
    }
};

int n;

int ran[MAX][2];

int si;
map<int, int> cmp;
int invc[2 * MAX + 1];

vector<prefixBinom> dp[2 * MAX + 1];
Mint psa[2 * MAX + 1];
void calcDP(int p) {
    for(int i = 0; i < si; i++) psa[i] = 0;
    int lb = cmp[ran[p][0]];
    int rb = cmp[ran[p][1] + 1];
    for(int i = 0; i < si; i++) {
        if(invc[i] == -1 || invc[i + 1] == -1) break;
        if(i != 0) psa[i] = psa[i - 1];
        if(i < rb) for(auto& j: dp[i]) psa[i] += j.calcVal();
        int cs = invc[i + 1] - invc[i];
        if(lb <= i && i < rb) {
            for(auto& j: dp[i]) j.incDegree();
            dp[i].push_back(prefixBinom(cs, psa[i - 1]));
        }
    }
}

void solve() {
    calcQinv();
    cin >> n;
    cmp[0];
    for(int i = 0; i < n; i++) {
        cin >> ran[i][0] >> ran[i][1];
        cmp[ran[i][0]];
        cmp[ran[i][1] + 1];
    }
    memset(invc, -1, sizeof(invc));
    for(auto& [i, j]: cmp) {
        invc[si] = i;
        j = si++;
    }
    int lb = cmp[ran[0][0]];
    int rb = cmp[ran[0][1] + 1];
    dp[0].push_back(prefixBinom(1, Mint(1)));
    for(int i = lb; i < rb; i++) {
        int ranl = invc[i];
        int ranr = invc[i + 1];
        dp[i].push_back(prefixBinom(ranr - ranl, Mint(1)));
    }
    for(int i = 1; i < n; i++) calcDP(i);
    Mint ans = 0;
    for(int i = 0; i < si; i++) {
        for(auto& j: dp[i]) ans += j.calcVal();
    }
    cout << ans - 1 << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    //cin >> t;
    t = 1;
    while(t--) solve();
}

Compilation message (stderr)

boat.cpp: In function 'void solve()':
boat.cpp:165:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  165 |     for(auto& [i, j]: cmp) {
      |               ^

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