Submission #1033315

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033315		borisAngelov	Trains (BOI24_trains)	C++17	Compilation error	0 ms	0 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100005;
const int BLOCK_SIZE = 355;
const int mod = 1e9 + 7;

int n;
int d[maxn], x[maxn];
int dp[maxn];
int pref[maxn];

int prefSmall[BLOCK_SIZE][BLOCK_SIZE];
vector<tuple<int, int, int>> toRemove[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> d[i] >> x[i];
    }

    int big = max(1, sqrt(n));
    int ans = 0;

    for (int i = 1; i <= n; ++i)
    {
        for (auto [small, rem, value] : toRemove[i])
        {
            prefSmall[small][rem] -= value;
            if (prefSmall[small][rem] < 0) prefSmall[small][rem] += mod;
        }

        if (i == 1)
        {
            dp[i] = 1;
        }
        else
        {
            for (int small = 1; small < big; ++small)
            {
                dp[i] += prefSmall[small][i % small];
                if (dp[i] >= mod) dp[i] -= mod;
            }
        }

        if (d[i] >= big)
        {
            for (int j = i + d[i]; j <= n; j += d[i])
            {
                dp[j] += dp[i];
                if (dp[j] >= mod) dp[j] -= mod;
            }
        }
        else if (d[i] != 0)
        {
            prefSmall[d[i]][i % d[i]] += dp[i];
            if (prefSmall[d[i]][i % d[i]] >= mod) prefSmall[d[i]][i % d[i]] -= mod;
            toRemove[min(1LL * n + 1LL, i + (1LL * x[i]) * (1LL * d[i]) + 1LL)].push_back({d[i], i % d[i], dp[i]});
        }

        ans += dp[i];
        if (ans >= mod) ans -= mod;

        //cout << i << " :: " << dp[i] << endl;
    }

    cout << ans << endl;

    return 0;
}

/*
5
1 3
1 1
0 4
1 2
1 2

5
1 3
1 1
1 2
1 2
1 2
2 :: 1
3 :: 2
4 :: 3
5 :: 5

12
3 1000000000
5 1000000000
2 1000000000
7 1000000000
4 1000000000
1 1000000000
1 1000000000
5 1000000000
2 1000000000
1 1000000000
1 1000000000
3 1000000000
here 2 :: 0
here 3 :: 0
here 4 :: 1
here 5 :: 0
here 6 :: 0
here 7 :: 1
here 8 :: 1
here 9 :: 1
here 10 :: 2
here 11 :: 5
here 12 :: 8
*/

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:35:29: error: no matching function for call to 'max(int, __gnu_cxx::__enable_if<true, double>::__type)'
   35 |     int big = max(1, sqrt(n));
      |                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:254:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  254 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:254:5: note:   template argument deduction/substitution failed:
Main.cpp:35:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'})
   35 |     int big = max(1, sqrt(n));
      |                             ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:300:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  300 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:300:5: note:   template argument deduction/substitution failed:
Main.cpp:35:29: note:   deduced conflicting types for parameter 'const _Tp' ('int' and '__gnu_cxx::__enable_if<true, double>::__type' {aka 'double'})
   35 |     int big = max(1, sqrt(n));
      |                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3480:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3480 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3480:5: note:   template argument deduction/substitution failed:
Main.cpp:35:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   35 |     int big = max(1, sqrt(n));
      |                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from Main.cpp:1:
/usr/include/c++/10/bits/stl_algo.h:3486:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3486 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3486:5: note:   template argument deduction/substitution failed:
Main.cpp:35:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   35 |     int big = max(1, sqrt(n));
      |                             ^