Submission #1047205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1047205		raczek	Trains (BOI24_trains)	C++17	100 / 100	474 ms	133552 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
#define int long long
const int MOD = 1e9+7;
const int SQRT = 320;
struct sqrtStruct
{
	vector<vector<int> > res;
	sqrtStruct()
	{
		res.resize(SQRT+1);
		for(int i=1;i<=SQRT;i++) res[i].resize(i);
	}
	void update(int pos, int val)
	{
		debug(pos);
		debug(val);
		pos %= SQRT;
		for(int i=1;i<=SQRT;i++)
		{
			res[i][pos%i] += val;
			res[i][pos%i] %= MOD;
		}
	}
	int get(int d, int mod)
	{
		return res[d][mod];
	}
};
int32_t main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<int> dp(n);
	vector<pair<int, int> > trains(n);
	for(auto& v : trains) cin>>v.first>>v.second;
	vector<sqrtStruct> sqrts(n/SQRT+1);
	for(int i=n-1;i>=0;i--)
	{
		debug(i);
		int d = trains[i].first, x = trains[i].second;
		if(d == 0 || x == 0) continue;
		if(d > SQRT)
		{
			for(int k = i+d;k<=i+d*x && k < n;k+=d)
			{
				dp[i] += dp[k] + 1;
				dp[i] %= MOD;
			}
		}
		else
		{
			dp[i] += (min(i + d*x, n-1) - i)/d;
			dp[i] %= MOD;
			debug(dp[i]);
			int k = i + d;
			for(;x > 0 && k < n && k < SQRT*(i/SQRT + 1);k+=d)
			{
				dp[i] += dp[k];
                                dp[i] %= MOD;
				x--;
			}
			k -= d;
			debug(dp[i]);
			int c = (i/SQRT + 1);
			for(; x >= (SQRT - 1 - (k+d)%SQRT)/d + 1 && c < sqrts.size(); c++)
			{
				debug(k);
				debug(x);			
				debug(sqrts[c].res);
				dp[i] += sqrts[c].get(d, (k+d)%SQRT);
				x -= (SQRT - 1 - (k+d)%SQRT)/d + 1;	
				k += ((SQRT - 1 - (k+d)%SQRT)/d + 1)*d;
				dp[i] %= MOD;
			}
			debug(dp[i]);
			k += d;
			for(;x > 0 && k < n;k+=d)
			{
				dp[i] += dp[k];
				dp[i] %= MOD;
				x--;
			}
		}
		debug(i/SQRT);
		sqrts[i/SQRT].update(i, dp[i]);
	}
	debug(dp);
	cout<<(dp[0]+1)%MOD;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:76:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<sqrtStruct>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   76 |    for(; x >= (SQRT - 1 - (k+d)%SQRT)/d + 1 && c < sqrts.size(); c++)
      |                                                ~~^~~~~~~~~~~~~~

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