Submission #433896

#	Time	Username	Problem	Language	Result	Execution time	Memory
433896		someone	Boat (APIO16_boat)	C++14	31 / 100	719 ms	524292 KiB

boat

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

struct Val {
    int i, val;
};

const int M = 1 << 20, N = 2 * M, T = 542, MOD = 1e9 + 7;

int node[N];
int a[T], b[T];
vector<Val> p;

int getSum(int i) {
    if(i <= 1)
        return 0;
    int sum = getSum(i/2);
    if(i % 2 == 1)
        sum += node[i-1];
    return sum % MOD;
}

void add(int i, int val) {
    if(i == 0)
        return;
    node[i] = (node[i] + val) % MOD;
    add(i/2, val);
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;
    int sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> a[i] >> b[i];
        sum += b[i] - a[i] + 1;
    }

    if(sum > M)
        return 0;

    for(int i = 0, x = 0; i < n; i++)
        for(int j = b[i]; j >= a[i]; j--, x++)
            p.push_back({x, j});

    sort(p.begin(), p.end(),
    [](Val v1, Val v2) {
        return v1.val < v2.val;
    });
    int pre = p[0].val;
    p[0].val = 1;
    int t = p.size();
    for(int i = 1; i < t; i++) {
        bool eq = (pre != p[i].val);
        pre = p[i].val;
        p[i].val = p[i-1].val + eq;
    }

    sort(p.begin(), p.end(),
    [](Val v1, Val v2) {
        return v1.i < v2.i;
    });

    sum = 0;
    for(int i = 0; i < t; i++) {
        int val = (getSum(p[i].val + M) + 1) % MOD;
        add(p[i].val + M, val);
        sum = (sum + val) % MOD;
    }
    cout << sum;
}

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