Submission #1033599

#	Time	Username	Problem	Language	Result	Execution time	Memory
1033599		Thanhs	Trains (BOI24_trains)	C++17	100 / 100	880 ms	234772 KiB

Main

// #pragma GCC optimize("Ofast")
// #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define double long double
 
#define endl '\n'
#define fastIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define setmin(x, y) x = min((x), (y))
#define setmax(x, y) x = max((x), (y))
#define sqr(x) ((x) * (x))
#define fi first
#define se second
#define all(x) x.begin(), x.end()
 
// mt19937 hdp(chrono::high_resolution_clock::now().time_since_epoch().count());
// int rand(int l, int r){return l + ((hdp() % (r - l + 1)) + r - l + 1) % (r - l + 1);}

const int NM = 1e5 + 5;
const int mod =  1e9 + 7;

int add(int x, int y)
{
    x += y;
    if (x >= mod)
        x -= mod;
    if (x < 0)
        x += mod;
    return x;
}

void adds(int& x, int y)
{
    x = add(x, y);
}

vector<int> c[NM];
vector<pair<pair<int, int>, int>> q[NM];
int n, d[NM], x[NM],  dp[NM], p[NM], ptr[NM];
vector<pair<int, int>> v;
map<pair<int, int>, int> mp;

signed main()
{
    fastIO
    if (fopen("in.txt", "r")) 
    {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> d[i] >> x[i];
        if (d[i])
            v.push_back({d[i], i % d[i]});
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    for (int i = 0; i < v.size(); i++)
    {
        mp[v[i]] = i; 
        for (int j = v[i].se; j <= n; j += v[i].fi)
            c[j].push_back(i);
    }
    for (int i = 1; i <= n; i++)
        if (d[i])
        {
            int t = mp[{d[i], i % d[i]}];
            q[t].push_back({{i + d[i], i}, 1});
            q[t].push_back({{i + d[i] * (x[i] + 1), i}, -1});
        }
    for (int i = 0; i < v.size(); i++)
        sort(q[i].begin(), q[i].end(), greater<pair<pair<int, int>, int>>());
    for (int i = n; i >= 1; i--)
    {
        adds(dp[i], 1);
        for (int j : c[i])
        {
            adds(p[j], dp[i]);
            while (ptr[j] < q[j].size() && q[j][ptr[j]].fi.fi >= i)
            {
                auto t = q[j][ptr[j]];
                if (t.fi.fi == i)
                    adds(dp[t.fi.se], p[j] * t.se);
                ptr[j]++;
            }
        }
    }
    cout << dp[1] << endl;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:61:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp:74:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i = 0; i < v.size(); i++)
      |                     ~~^~~~~~~~~~
Main.cpp:82:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   82 |             while (ptr[j] < q[j].size() && q[j][ptr[j]].fi.fi >= i)
      |                    ~~~~~~~^~~~~~~~~~~~~
Main.cpp:49:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 |         freopen("in.txt", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:50:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |         freopen("out.txt", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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