Submission #1111605

#	Time	Username	Problem	Language	Result	Execution time	Memory
1111605		itslq	Trains (BOI24_trains)	C++17	0 / 100	20 ms	604 KiB

Main

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

int N;
const int MAX = 1e5, MOD = 1e9 + 7;
vector<int> fenwick(MAX + 5);

void update(int n, int v) {
    for (; n <= N; n += n & -n) {
        fenwick[n] = (fenwick[n] + v) % MOD;
    }
}

int query(int n) {
    int S = 0;
    for (; n > 0; n -= n & -n) {
        S = (S + fenwick[n]) % MOD;
    }
    return S;
}

int main() {
    cin >> N;
    int D, X, S = 0;
    update(1, 1);
    for (int i = 1; i <= N; i++) {
        cin >> D >> X;
        const int Q = query(i);
        update(i + 1, Q);
        update(i + X + 1, -Q);
    }

    for (int i = 1; i <= N; i++) {
        S = (S + query(i)) % MOD;
    }

    cout << (S + MOD) % MOD;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 13
• Subtask 3: 0 / 16
• Subtask 4: 0 / 34
• Subtask 5: 0 / 29