Submission #679229

#	Time	Username	Problem	Language	Result	Execution time	Memory
679229		bebra	Boat (APIO16_boat)	C++17	31 / 100	489 ms	524288 KiB

boat

#include <bits/stdc++.h>
using namespace std;

#define dbg(x) cerr << #x << ": " << x << endl;


const int MOD = 1e9 + 7;

int add(int a, int b) {
    int res = a + b;
    if (res >= MOD) {
        res -= MOD;
    }
    return res;
}

int mul(long long a, int b) {
    return a * b % MOD;
}

const int MAX_N = 500 + 1;
int a[MAX_N];
int b[MAX_N];
vector<int> dp[MAX_N];


struct FenwickTree {
    vector<int> tree;
    int size;

    FenwickTree(int n) {
        size = n;
        tree.resize(size);
    }

    void update(int pos, int value) {
        for (int i = pos; i < size; i |= i + 1) {
            tree[i] = add(tree[i], value); 
        }
    }

    int query(int pos) {
        int res = 0;
        for (int i = pos; i >= 0; i = (i & (i + 1)) - 1) {
            res = add(res, tree[i]);
        }
        return res;
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> as = {0};
    for (int i = 1; i <= n; ++i) {
        cin >> a[i] >> b[i];
        for (int j = a[i]; j <= b[i]; ++j) {
            as.push_back(j);
        }
    }
    sort(as.begin(), as.end());
    as.resize(unique(as.begin(), as.end()) - as.begin());
    dp[0].assign(1, 1);
    a[0] = -1;
    b[0] = -1;
    FenwickTree pref(as.size());
    pref.update(0, 1);
    int ans = 0;
    for (int i = 1; i <= n; ++i) {
        dp[i].resize(b[i] - a[i] + 1);
        int m = dp[i].size();
        int pos = lower_bound(as.begin(), as.end(), a[i]) - as.begin();
        int pos0 = pos;
        for (int j = 0; j < m; ++j) {
            int x = a[i] + j;
            while (as[pos] < x) ++pos;
            dp[i][j] = pref.query(pos - 1);
        }
        for (int j = 0; j < m; ++j) {
            int x = a[i] + j;
            while (as[pos0] < x) ++pos0;
            pref.update(pos0, dp[i][j]);
            ans = add(ans, dp[i][j]);
        }
    }
    cout << ans << '\n';
    return 0;
}

/*
*/

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