oj.uz

Submission #993550

# Submission time Handle Problem Language Result Execution time Memory
993550 2024-06-06T04:46:54 Z AlperenT_ Trains (BOI24_trains) C++17
58 / 100
 166 ms 272208 KB 
#include <bits/stdc++.h>
 
#pragma GCC optimize("O3,unroll-loops")
#define pb push_back
#define F first
#define S second 
#define all(a) a.begin(),a.end()
#define pii pair <int,int>
#define PII pair<pii , pii>
#define ld long double
#define int long long 
#define sz(v) (int)v.size()
#define rep(i , a , b) for(int i=a;i <= b;i++)
#define per(i, a , b) for(int i=a;i >= b;i--)
using namespace std ;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2e5+10  ,  N = 1e5 +1 , lg = 20 , maxq = 202 , sq = 333   , inf = 1e18  , maxk = 2022  , mod =1e9 + 7;
int s[maxn][sq+2] , d[maxn] , x[maxn] , ans[maxn] ; 
vector <int> vec[maxn] ; 

signed main(){
  ios_base::sync_with_stdio(false); cin.tie(0);   
  int n ;
  cin >> n ;
  rep(i , 1, n){
    cin >> d[i] >> x[i] ;
    if(d[i] <= sq && i+d[i]*(x[i] + 1) <= n){
      vec[i+d[i]*(x[i]+1)].pb(i); 
    }
  }
  per(i , n , 1){
    if(d[i] <= sq){
      ans[i] = (ans[i] + 1 + s[i+d[i]][d[i]] )%mod ; 
    }else{
      ans[i] =1 ;
      for(int j = 1 ; j <= x[i] && j*d[i] <= n ; j++){
        ans[i] = (ans[i] + ans[j])%mod ;
      }
    }
    rep(j ,1  , sq){
      s[i][j] = (ans[i]+ s[i+j][j])%mod ;
    }
    for(int x : vec[i]){
      ans[x] = (ans[x] - s[i][d[x]] + mod)%mod ;
    }
  }
  cout << ans[1] << "\n" ;
}

/*

*/

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8848 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 1 ms 8792 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8848 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 1 ms 8792 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 9 ms 30552 KB Output is correct
21 Incorrect 4 ms 17660 KB Output isn't correct
22 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 9 ms 26804 KB Output is correct
3 Correct 6 ms 21592 KB Output is correct
4 Correct 9 ms 31064 KB Output is correct
5 Correct 113 ms 214164 KB Output is correct
6 Correct 142 ms 272016 KB Output is correct
7 Correct 166 ms 272208 KB Output is correct
8 Correct 2 ms 8792 KB Output is correct
9 Correct 2 ms 8796 KB Output is correct
10 Correct 2 ms 8796 KB Output is correct
11 Correct 11 ms 36060 KB Output is correct
12 Correct 150 ms 271860 KB Output is correct
13 Correct 2 ms 8804 KB Output is correct
14 Correct 11 ms 36072 KB Output is correct
15 Correct 147 ms 272020 KB Output is correct

Subtask #4
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 135028 KB Output is correct
2 Correct 56 ms 113636 KB Output is correct
3 Correct 144 ms 272044 KB Output is correct
4 Correct 102 ms 196432 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 2 ms 8872 KB Output is correct
7 Correct 12 ms 35036 KB Output is correct
8 Correct 139 ms 271972 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8796 KB Output is correct
2 Correct 2 ms 8796 KB Output is correct
3 Correct 1 ms 8792 KB Output is correct
4 Correct 1 ms 8796 KB Output is correct
5 Correct 2 ms 8796 KB Output is correct
6 Correct 1 ms 8796 KB Output is correct
7 Correct 2 ms 8796 KB Output is correct
8 Correct 2 ms 8848 KB Output is correct
9 Correct 1 ms 8796 KB Output is correct
10 Correct 1 ms 8796 KB Output is correct
11 Correct 1 ms 8796 KB Output is correct
12 Correct 1 ms 8792 KB Output is correct
13 Correct 1 ms 8796 KB Output is correct
14 Correct 2 ms 8796 KB Output is correct
15 Correct 1 ms 8792 KB Output is correct
16 Correct 1 ms 8796 KB Output is correct
17 Correct 1 ms 8796 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 2 ms 8796 KB Output is correct
20 Correct 9 ms 30552 KB Output is correct
21 Incorrect 4 ms 17660 KB Output isn't correct
22 Halted 0 ms 0 KB -