fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. #define ll long long
  4. #define el cout << '\n'
  5. #define ngay_xua_em_che_toi_code_ga ios_base::sync_with_stdio(0);
  6. #define bay_gio_toi_da_tat_luon cin.tie(0);
  7. #define em_da_thay_hoi_han_chua cout.tie(0);
  8.  
  9. using namespace std;
  10.  
  11. const int maxn = 5e6;
  12. const int MOD = 1e9 + 7;
  13.  
  14. int n, l[maxn + 10], r[maxn + 10];
  15. ll dp[maxn + 10], diff[maxn + 10];
  16.  
  17. void add(ll &a, ll b)
  18. {
  19.     a += b;
  20.     if (a >= MOD) a -= MOD;
  21.     if (a < 0) a += MOD;
  22. }
  23.  
  24. int main()
  25. {
  26.     ngay_xua_em_che_toi_code_ga
  27.     bay_gio_toi_da_tat_luon
  28.     em_da_thay_hoi_han_chua
  29.  
  30.     if (fopen("TAU_DIEN_MOTRE.INP", "r"))
  31.     {
  32.         freopen("TAU_DIEN_MOTRE.INP", "r", stdin);
  33.         freopen("TAU_DIEN_MOTRE.OUT", "w", stdout);
  34.     }
  35.  
  36.     cin >> n;
  37.     for (int i = 1; i < n; i++)
  38.         cin >> l[i] >> r[i];
  39.     add(diff[1], 1);
  40.     add(diff[2], -1);
  41.     for (int i = 1; i <= n; i++)
  42.     {
  43.         dp[i] = dp[i - 1];
  44.         add(dp[i], diff[i]);
  45.         add(diff[l[i]], dp[i]);
  46.         add(diff[r[i] + 1], -dp[i]);
  47.     }
  48.     for (int i = 2; i <= n; i++)
  49.         cout << dp[i] << ' ';
  50. }
Success #stdin #stdout 0.01s 7676KB
comments (?)
stdin
copy 
10
2 2
3 5
8 9
5 8
9 9
8 10
8 9
9 10
stdout
copy 
1 1 1 2 1 1 4 9 5
https://ideone.com/54EkNC
language:
C++14 (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!