fork download 
  1. //satyaki3794
  2. #include <bits/stdc++.h>
  3. #define ff first
  4. #define ss second
  5. #define pb push_back
  6. #define MOD (1000000007LL)
  7. #define LEFT(n) (2*(n))
  8. #define RIGHT(n) (2*(n)+1)
  9.  
  10. using namespace std;
  11. typedef long long ll;
  12. typedef pair<int, int> ii;
  13. typedef pair<int, ii> iii;
  14.  
  15. ll pwr(ll base, ll p, ll mod=MOD){
  16. base %= mod;
  17. ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
  18. }
  19.  
  20.  
  21. ll gcd(ll a, ll b){
  22.     if(b == 0)  return a;
  23.     return gcd(b, a%b);
  24. }
  25.  
  26.  
  27.  
  28. const int N = 200002;
  29. int n, sparse[20][N];
  30. ll DP[N];
  31.  
  32.  
  33. int rmq(int l, int r){
  34.     int k = log2(r-l+1);
  35.     return min(sparse[k][l], sparse[k][r-(1<<k)+1]);
  36. }
  37.  
  38.  
  39. int main(){
  40.  
  41.     // ios_base::sync_with_stdio(0);
  42.     // cin.tie(0);
  43.  
  44.     int q;
  45.     scanf("%d%d", &n, &q);
  46.     for(int i=1;i<=n;i++)
  47.         sparse[0][i] = n+1;
  48.  
  49.     while(q--){
  50.         int l, r;
  51.         scanf("%d%d", &l, &r);
  52.         sparse[0][l] = min(sparse[0][l], r);
  53.     }
  54.  
  55.     for(int j=1;(1<<j)<=n;j++)
  56.         for(int i=1;i+(1<<j)-1<=n;i++)
  57.             sparse[j][i] = min(sparse[j-1][i], sparse[j-1][i+(1<<(j-1))]);
  58.  
  59.     DP[n+1] = 1;
  60.     for(int i=n;i>=1;i--){
  61.         int max_allowed = i, lo = i, hi = n;
  62.         while(lo <= hi){
  63.             int mid = (lo+hi)/2;
  64.             if(rmq(i, mid) >= mid){
  65.                 max_allowed = max(max_allowed, mid);
  66.                 lo = mid+1;
  67.             }
  68.             else{
  69.                 hi = mid-1;
  70.             }
  71.         }
  72.         ll temp = DP[i+1] - DP[max_allowed+2];
  73.         if(rmq(i, n) == n+1)  temp++;
  74.         DP[i] = (DP[i+1] + temp) % MOD;
  75.     }
  76.  
  77.     ll ans = (DP[1]-DP[2]+MOD) % MOD;
  78.     printf("%lld\n", ans);
  79.     return 0;
  80. }
  81.  
  82.  
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
Runtime error #stdin #stdout 0s 4500KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/0cMSzo
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
secret

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!