Submission #1058782

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058782		Tonyl	Trains (BOI24_trains)	C++17	16 / 100	16 ms	3036 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vi = vector<int>;
using pi = pair<int,int>;
#define REP(i,n) for (int i = 0; i < n; i++)
#define trav(a,x) for (auto& a : x)
#define D(x) cerr << #x << ": " << x << endl;
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9+7;
const int MAX_N = 1e5+1;

struct Prefix {
    vi pr = {0};

    int q(int x) {
        if (x <= 0) return 0;
        int r = pr.back();
        int l = pr.size()>x ? pr[pr.size()-1-x] : 0;
        return (MOD+r-l)%MOD;
    }

    void add(int a) {
        pr.push_back((pr.back()+a)%MOD);
    }
};

struct Station {
    int d, x;
};

Station st[MAX_N];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    int n; cin >> n;
    REP(i,n) {
        cin >> st[i].d >> st[i].x;
    }

    Prefix ones;

    for (int i = n-1; i >= 0; i--) {
        ones.add(ones.q(st[i].x)+1);
        //D(ones.pr.back());
    }

    cout << ones.q(1) << endl;

}

Compilation message (stderr)

Main.cpp: In member function 'int Prefix::q(int)':
Main.cpp:20:26: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |         int l = pr.size()>x ? pr[pr.size()-1-x] : 0;
      |                 ~~~~~~~~~^~

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