Submission #1058812

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058812		Tonyl	Trains (BOI24_trains)	C++17	100 / 100	448 ms	191916 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;
const int SQRT = 320;

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 stations[MAX_N];
Prefix prsq[SQRT][SQRT+1];
int totals[MAX_N];

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

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

    for (int i = n-1; i >= 0; i--) {
        Station& st = stations[i];
        int tot = 1;
        if (st.d >= SQRT) {
            int j = i+st.d;
            while (j < n && st.x--) {
                tot += totals[j];
                j += st.d;
                tot %= MOD;
            }
        } else if (st.d != 0) tot = prsq[st.d-1][i%st.d].q(st.x)+1;
        for (int s = 0; s < SQRT; s++) {
            int sq = s+1;
            int md = i%sq;
            prsq[s][md].add(tot);
        }
        totals[i] = tot;
    }

    cout << totals[0] << endl;

}

Compilation message (stderr)

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

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