Submission #1097609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097609		Yadav1992	Trains (BOI24_trains)	C++14	100 / 100	794 ms	10704 KiB

Main

#include <bits/stdc++.h>
#include <vector>
#include <iostream>
using namespace std;
#define ll long long
#define mod 1000000007

ll calculateTotal(vector<ll> &dp){
    ll total = 0;
    for(auto entry : dp){
        total += entry;
        total %= mod;
    }
    return total;
}

ll processPrev(unordered_map<ll, unordered_map<ll, ll> > &pending, ll index) {
    ll answer = 0;
    for(auto& entry : pending){
        ll d = entry.first;
        auto& countMap = entry.second;
        if(countMap.find(index % d) != countMap.end()){
            answer += countMap[index % d];
            answer %= mod;
        }
    }
    return answer;
}

void addNext(ll d, ll x, ll index, ll count, ll n, unordered_map<ll, unordered_map<ll, ll> > &pending,
    unordered_map<ll, vector<vector<ll> > > &ending) 
{
    ll i = index % d;
    vector<ll> end(3);
    end[0] = d;
    end[1] = i;
    end[2] = count;
    ll endIndex = index + d * x;
    if(endIndex > n){
        endIndex = n;
    }
    if(pending.find(d) == pending.end()){
        pending[d] = unordered_map<ll, ll>();
    }
    pending[d][i] += count;

    if(ending.find(endIndex) == ending.end()){
        ending[endIndex] = vector<vector<ll> >();
    }
    ending[endIndex].push_back(end);

}

void addNext(ll d, ll x, ll index, vector<ll> & dp)
{
    ll value = dp[index];
    ll n = (ll)dp.size();
    for(ll i = index + d; (i < n) && (i <= (index + d * x)); i+= d) {
        dp[i] += value;
        dp[i] %= mod;
    }
}

void deletePrev(unordered_map<ll, unordered_map<ll, ll> > & pending,
    unordered_map<ll, vector<vector<ll> > > & ending, ll index)
{
    if(ending.find(index) != ending.end()){
        auto & entries = ending[index];
        for(auto & entry : entries){
            ll d = entry[0], i = entry[1], count = entry[2];
            pending[d][i] += mod - count;
            pending[d][i] %= mod;
            if(pending[d][i] == 0) {
                pending[d].erase(i);
            }
        }
        ending.erase(index);
    }
}

void solve(ll n, vector<ll> &D, vector<ll> &X)
{
    unordered_map<ll, unordered_map<ll, ll> > pending;
    unordered_map<ll, vector<vector<ll> > > ending;
    vector<ll> dp(n, 0);
    dp[0] = 1;
    for(int i = 0; i < n; i++) {
        dp[i] += processPrev(pending, i);
        dp[i] %= mod;
        deletePrev(pending, ending, i);
        if(D[i] == 0 || X[i] == 0) continue;
        if(D[i] < (ll)sqrt(n) && X[i] > 0){
            addNext(D[i], X[i], i, dp[i], n, pending, ending);
        } else if (X[i] > 0) {
            addNext(D[i], X[i], i, dp);
        }
    }    
    cout << calculateTotal(dp);
}

int main() {
    ll n=1;
    cin>>n;
    vector<ll> D;
    vector<ll> X;
    ll i = n;
    if(n == 0){
        cout << 1;
        return 0;
    }
    while(i--)
    {
        ll d, x;
        cin >> d >> x;
        D.push_back(d);
        X.push_back(x);
    }
    solve(n, D, X);
    return 0;
}

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