이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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 = 2;
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;
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]);
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;
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int32_t main()':
Main.cpp:75:50: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<sqrtStruct>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
75 | for(; x >= (SQRT - 1 - (k+d)%SQRT)/d + 1 && c < sqrts.size(); c++)
| ~~^~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |