Submission #1169084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1169084		Bui_Quoc_Cuong	Trains (BOI24_trains)	C++20	24 / 100	2097 ms	6900 KiB

Main

/* 29 . 03 . 2008 */ 
#include <bits/stdc++.h>
using namespace std ;

bool watbor = 0 ;

#define int long long
typedef long long ll ;
typedef vector<int> vi ;
typedef vector<pair<int,int>> vii ;
typedef pair<int,int> pii ;
typedef pair<ll,int> pli ;
typedef pair<int,ll> pil ;
typedef pair<ll,ll> pll ;

#define FOR(i,a,b) for(int i(a) ; i <= (int)b ; i++)
#define FORD(i,a,b) for(int i(a) ; i >= (int)b ; i--)
#define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
#define all(a) a.begin() , a.end()
#define pb push_back
#define fi first
#define se second
#define endl '\n' 
#define BIT(mask,i) ((mask>>i)&1)
#define builtin_popcount builtin_popcountll
#define uni(a) sort(all(a)), a.resize(unique(all(a))-a.begin()) 
#define MASK(a) (1ll << a) 

int gcd(int x, int y) {return __gcd(x, y) ;}
int lg(int x) {return __lg(x) ;}
int lcm(int x, int y) {return x / __gcd(x, y) * y ;}

template <class T> bool maxi(T &x,T y) { if (x < y) { x = y ; return true ;} return false ;}
template <class T> bool mini(T &x,T y) { if (x > y) { x = y ; return true ;} return false ;}

const int N = 2e5 + 5, M = 5e3 + 5, LG = __lg(N) + 1, base = 311 ;
const int oo = 2e9, sm = 1e9 + 7, mod1 = 1e9 + 7, mod2 = 998244353 ;
const long long inf = 1e18 ;

void add(int &x, const int y) {
    x+= y ; 
    if(x >= sm) x-= sm ; 
}

int n ; 
pair <int, int> a[N] ;

void init() {
	cin >> n ;
	FOR(i, 1, n)
		cin >> a[i].fi >> a[i].se ;
}

namespace subtask_1 {
	bool check() {return n <= 5e3 ;}

    int dp[N] ;

	void solve() {
        dp[1] = 1 ; 

        FOR(i, 1, n) FOR(t, i + 1, n) {
            int so = (t - i) ; 
            if(a[i].fi == 0) continue ; 
            if(so % a[i].fi == 0 && so / a[i].fi <= a[i].se)
                add(dp[t], dp[i]) ; 
        }

        int ans = 0 ;
        FOR(i, 1, n) add(ans, dp[i]) ;
        cout << ans ; 
	}
}

namespace subtask_2 {
    bool check() {FOR(i, 1, n) if(a[i].fi != 1) return 0; return 1;}

    int dp[N] ;
    int st[4 * N], lazy[4 * N] ; 

    void down(int id, int l, int r) {
        if(lazy[id] == 0) return ; 

        int mid = (l + r) >> 1 ; 

        st[id << 1]+= 1ll * (mid - l + 1) * lazy[id] ; 
        st[id << 1 | 1]+= 1ll * (r - mid) * lazy[id] ; 

        if(st[id << 1] >= sm) st[id << 1] -= sm ; 
        if(st[id << 1 | 1] >= sm) st[id << 1 | 1] -= sm ; 

        lazy[id << 1]+= lazy[id] ; 
        lazy[id << 1 | 1]+= lazy[id] ; 

        if(lazy[id << 1] >= sm) lazy[id << 1]-= sm ; 
        if(lazy[id << 1 | 1] >= sm) lazy[id << 1 | 1]-= sm ; 

        lazy[id] = 0 ;
    }

    void up(int id, int l, int r, int u, int v, int val) {
        if(l > v || r < u) return ; 
        if(l >= u && r <= v) {
            st[id]+= 1ll * (r - l + 1) * val ;
            lazy[id]+= val ; 

            if(st[id] >= sm) st[id]-= sm ;
            if(lazy[id] >= sm) lazy[id]-= sm ; 
            return ; 
        }
        down(id, l, r) ; 
        int mid = (l + r) >> 1 ; 
        up(id << 1, l, mid, u, v, val) ; 
        up(id << 1 | 1, mid + 1, r, u, v, val) ; 
        st[id] = (st[id << 1] + st[id << 1 | 1]) % sm ; 
    }

    int get(int id, int l, int r, int u, int v) {
        if(l > v || r < u) return 0 ;
        if(l >= u && r <= v) return st[id] ; 
        int mid = (l + r) >> 1 ;
        down(id, l, r) ; 
        return (get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v) ) % sm ;
    }

    void solve() {
        dp[1] = 1 ; 
        up(1, 1, n, 1, min(n, 1 + a[1].se), 1) ; 

        FOR(i, 2, n) {
            dp[i] = get(1, 1, n, i, i) ; 
            up(1, 1, n, i + 1, min(n, i + a[i].se), dp[i]) ;
        }

        int ans = 0 ;
        FOR(i, 1, n) add(ans, dp[i]) ;
        cout << ans ;
    }
}

namespace subtask_3 {
    bool check() {
        FOR(i, 1, n) if(a[i].se != n) return 0 ;
        return 1 ; 
    }

    int dp[N] ;

    void solve() {
        FOR(i, 1, n) {
            if(i == 1) dp[i] = 1 ; 
            for(int j = 0; j <= a[i].se; j++) {
                if(i + 1ll * j * a[i].fi > n) break ; 
                if(i + 1ll * j * a[i].fi <= i) continue ; 
                add(dp[i + 1ll * j * a[i].fi], dp[i]) ;
            }
        }

        int ans = 0 ;
        FOR(i, 1, n) add(ans, dp[i]) ;
        cout << ans ; 
    }
}

int32_t main() {
    ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; 

    #define task ""
    if(fopen(task".inp","r")) {
        freopen(task".inp","r",stdin) ; 
        freopen(task".out","w",stdout) ; 
    }

    int tc ; tc = 1 ;
    if(watbor) cin >> tc ;

    FOR(bqc, 1, tc) {
        init() ;
        if(subtask_1::check()) return subtask_1::solve(), 0 ;
        if(subtask_2::check()) return subtask_2::solve(), 0 ;
        return subtask_3::solve(), 0 ; 
    }

    cerr << "\nTime : " << clock() * 0.001 << "s" << endl ;
    return 0 ; 
}
/* Watbor */

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:170:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  170 |         freopen(task".inp","r",stdin) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:171:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  171 |         freopen(task".out","w",stdout) ;
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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