Submission #1265089

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265089		MaksimOJ	Trains (BOI24_trains)	C++20	21 / 100	2116 ms	807600 KiB

Main

#include <bits/stdc++.h>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define all(x) x.begin(), x.end()
#define sz(x) ((int) ((x).size()))
#define print(x, y) for(auto it = x; it != y; it++){cout << *it << " ";}cout <<"\n";

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using ld = long double;
using P = pair<ld, ld>;

//using namespace __gnu_pbds;
//#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>


const int N = 2e5+5;
const int SQ = 400;
const ll INF = (ll)1e18;
const ll MOD = 1e9+7;
const int BAZA = 69313;

int n;
pii niz[N];
ll dp[N];
ll mat[SQ][SQ];
deque<pii> suf[SQ][SQ];

ll add(ll x, ll y){
	if(x + y < 0) return MOD + x + y;
	return (x + y) % MOD;
}

ll mul(ll x, ll y){
	return (x * y) % MOD;
}


int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	cin >> n;
	for(int i = 0; i< n; i++){
		cin >> niz[i].first >> niz[i].second;
		//if(niz[i].first != 0) niz[i].second = min((n - i) / niz[i].first, niz[i].second); 
	}
	/*
	cout << "____________\n";
	for(int i = 0; i < n; i++){
		cout << niz[i].first << " " << niz[i].second << "\n";
	}*/
	
	for(int i = n - 1; i >= 0; i--){
		dp[i] = 1;

		if(niz[i].first == 0);
		else if(niz[i].first >= SQ){
			//cout << "> " << sq << "\n";
			int cnt = 0;
			for(int j = i + niz[i].first; j < n; j += niz[i].first){
				cnt ++;
				if(cnt > niz[i].second) continue;
				dp[i] = add(dp[i], dp[j]);
				
			}
		}
		else{
			//cout << "ost: " << i % niz[i].first << " " << niz[i].first << "\n";
			//cout << "Adding " << mat[niz[i].first][i % niz[i].first] << "\n";
			//cout << "H1\n";
			dp[i] = add(dp[i], mat[niz[i].first][i % niz[i].first]);
			//cout << "ind " << i + niz[i].first * niz[i].second << "\n";
			//cout << "H1.1\n";
			auto it = upper_bound(suf[niz[i].first][i % niz[i].first].begin(), suf[niz[i].first][i % niz[i].first].end(), make_pair((ll)i + niz[i].first * niz[i].second, INF));
			//cout << "H2\n";
			if(it != suf[niz[i].first][i % niz[i].first].end()){
				
				int poz = it - suf[niz[i].first][i % niz[i].first].begin();
				//cout << "removing " << suf[niz[i].first][i % niz[i].first][poz].second << "\n";
				dp[i] = add(dp[i], -suf[niz[i].first][i % niz[i].first][poz].second);
			}
			//cout << "H3\n";
			//else cout << "no it\n";
		}
		//cout << "DP[" << i << "] = " << dp[i] << "\n";
		for(int j = 1; j < SQ; j++){
			mat[j][i % j] = add(mat[j][i % j], dp[i]);
			//cout << "H4\n";
			suf[j][i % j].push_front({i, dp[i]});
			//cout << "H5\n";
			if(suf[j][i % j].size() > 1) suf[j][i % j][0].second = add(suf[j][i % j][0].second, suf[j][i % j][1].second);
			//cout << "H6\n";
		}
	}
	cout << dp[0] << "\n";
	return 0;
}

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