fork download 
  1. #include <iostream>
  2. #include <algorithm>
  3. #define int long long
  4.  
  5.  
  6. using namespace std;
  7.  
  8. constexpr int N = 1111 + 5;
  9. constexpr int P = 1e9 + 9999;
  10. int n;
  11. pair<int, int> ranges[N];
  12.  
  13. int inv[N] = {0};
  14. int a[N];
  15.  
  16. int invert(int x) {
  17.     int y = 1;
  18.     for (int k = P - 2; k; k >>= 1) {
  19.         if (k & 1)
  20.             y = y * x % P;
  21.         x = x * x % P;
  22.     }
  23.     return y;
  24. }
  25.  
  26. void init() {
  27.     inv[1] = 1;
  28.     for (int p = 2; p < N; p++) {
  29.         if (inv[p]) continue;
  30.         inv[p] = invert(p);
  31.         for (int k = p; k * p < N; k++) {
  32.             inv[k * p] = inv[k] * inv[p] % P;
  33.         }
  34.     }
  35. }
  36.  
  37. int get(int x)
  38. {
  39.     int y = 1;
  40.     int res = 0;
  41.     for (int k = 0; k <= n; k++) {
  42.         y = y * (x - k + P) % P;
  43.         res = (res + a[k] * y % P * inv[k + 1]) % P;
  44.     }
  45.     return res;
  46. }
  47.  
  48. signed main()
  49. {
  50.     ios::sync_with_stdio(false);
  51.     cin.tie(NULL);
  52.     cout.tie(NULL);
  53.  
  54.     // freopen("input.txt", "r", stdin);
  55.     // freopen("maxvalue.inp", "r", stdin);
  56.     // freopen("maxvalue.out", "w", stdout);
  57.  
  58.     init();
  59.  
  60.     cin >> n;
  61.  
  62.     int prod = 1;
  63.  
  64.     int maxl = 0;
  65.     int maxr = 0;
  66.     for (int i = 1; i <= n; i++) {
  67.         int l, r;
  68.         cin >> l >> r;
  69.         r++;
  70.         ranges[i] = {l, r};
  71.  
  72.         maxl = max(maxl, l);
  73.         maxr = max(maxr, r);
  74.         prod = prod * (r - l) % P;
  75.     }
  76.     int U = prod * maxr % P;
  77.  
  78.     ranges[0] = {0, maxl};
  79.     sort(ranges + 1, ranges + n + 1,
  80.       [](const pair<int, int> &lr1, const pair<int, int> &lr2) {
  81.         return lr1.second < lr2.second;
  82.     });
  83.  
  84.     int ans = 0;
  85.  
  86.     a[0] = 1;
  87.     for (int i = 1; i <= n; i++)
  88.         a[i] = 0;
  89.  
  90.     for (int i = n; i; i--) {
  91.         int L = ranges[i].first;
  92.         int R = ranges[i].second;
  93.         int lo = max(maxl, ranges[i - 1].second);
  94.  
  95.         for (int k = n; k >= 0; k--) {
  96.             a[k] = a[k] * (k - L + P);
  97.             if (k > 0) a[k] += a[k - 1];
  98.             a[k] %= P;
  99.         }
  100.  
  101.         prod = prod * invert(R - L) % P;
  102.  
  103.         ans += (get(R + 1) - get(lo + 1) + P) * prod % P;
  104.         if (lo == maxl) break; 
  105.     }
  106.  
  107.     cout << ((U - ans + P) % P + P) % P;
  108.  
  109.     return 0;
  110. }
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/JojrPT
language:
C++14 (gcc 8.3)
created:
8 days 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!