Submission #39788

#	Time	Username	Problem	Language	Result	Execution time	Memory
39788		nickyrio	Boat (APIO16_boat)	C++14	31 / 100	312 ms	524288 KiB

boat

#include <bits/stdc++.h>
#define FOR(i, a, b) for (int i = a, _b = b; i <= _b; ++i)
#define FORD(i, a, b) for (int i = a, _b = b; i >= _b ; --i)
#define REP(i, a) for (int i = 0, _a = a; i < a; ++i)
#define pp pair<int, int>
#define bit(S, i) (((S) >> i) & 1)
#define next __next
#define prev __prev
#define N 1000100
#define NN 1111
#define taskname ""
using namespace std;

int n, a[N], b[N];
const long long MOD = 1e9 + 7;
long long BIT[N];
long long Get(int u) {
    long long ans = 0;
    for (; u > 0 ; u -= u & -u) ans = (ans + BIT[u]) % MOD;
    return ans;
}

void Up(int u, long long val) {
    for (; u < N; u += u & -u) BIT[u] = (BIT[u] + val) % MOD;
}
vector<int> e;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n;
    FOR(i, 1, n) {
        cin >> a[i] >> b[i];
        FOR(j, a[i], b[i]) e.push_back(j);
    }
    e.push_back(0);
    sort(e.begin(), e.end());
    e.resize(unique(e.begin(), e.end()) - e.begin());
    Up(1, 1);
    long long ans = 0;
    FOR(i, 1, n) {
        FORD(k, b[i], a[i]) {
            int p = lower_bound(e.begin(), e.end(), k) - e.begin() + 1;
            long long now = Get(p - 1);
            Up(p, now);
            ans = (ans + now) % MOD;
        }
    }
    cout << ans;
}

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