fork download
copy 
  1. // #pragma GCC target("avx")
  2. // #pragma GCC optimize(3)
  3. // #pragma GCC optimize("Ofast")
  4. // #pragma GCC optimize("inline")
  5. // #pragma GCC optimize("-fgcse")
  6. // #pragma GCC optimize("-fgcse-lm")
  7. // #pragma GCC optimize("-fipa-sra")
  8. // #pragma GCC optimize("-ftree-pre")
  9. // #pragma GCC optimize("-ftree-vrp")
  10. // #pragma GCC optimize("-fpeephole2")
  11. // #pragma GCC optimize("-ffast-math")
  12. // #pragma GCC optimize("-fsched-spec")
  13. // #pragma GCC optimize("unroll-loops")
  14. // #pragma GCC optimize("-falign-jumps")
  15. // #pragma GCC optimize("-falign-loops")
  16. // #pragma GCC optimize("-falign-labels")
  17. // #pragma GCC optimize("-fdevirtualize")
  18. // #pragma GCC optimize("-fcaller-saves")
  19. // #pragma GCC optimize("-fcrossjumping")
  20. // #pragma GCC optimize("-fthread-jumps")
  21. // #pragma GCC optimize("-funroll-loops")
  22. // #pragma GCC optimize("-fwhole-program")
  23. // #pragma GCC optimize("-freorder-blocks")
  24. // #pragma GCC optimize("-fschedule-insns")
  25. // #pragma GCC optimize("inline-functions")
  26. // #pragma GCC optimize("-ftree-tail-merge")
  27. // #pragma GCC optimize("-fschedule-insns2")
  28. // #pragma GCC optimize("-fstrict-aliasing")
  29. // #pragma GCC optimize("-fstrict-overflow")
  30. // #pragma GCC optimize("-falign-functions")
  31. // #pragma GCC optimize("-fcse-skip-blocks")
  32. // #pragma GCC optimize("-fcse-follow-jumps")
  33. // #pragma GCC optimize("-fsched-interblock")
  34. // #pragma GCC optimize("-fpartial-inlining")
  35. // #pragma GCC optimize("no-stack-protector")
  36. // #pragma GCC optimize("-freorder-functions")
  37. // #pragma GCC optimize("-findirect-inlining")
  38. // #pragma GCC optimize("-fhoist-adjacent-loads")
  39. // #pragma GCC optimize("-frerun-cse-after-loop")
  40. // #pragma GCC optimize("inline-small-functions")
  41. // #pragma GCC optimize("-finline-small-functions")
  42. // #pragma GCC optimize("-ftree-switch-conversion")
  43. // #pragma GCC optimize("-foptimize-sibling-calls")
  44. // #pragma GCC optimize("-fexpensive-optimizations")
  45. // #pragma GCC optimize("-funsafe-loop-optimizations")
  46. // #pragma GCC optimize("inline-functions-called-once")
  47. // #pragma GCC optimize("-fdelete-null-pointer-checks")
  48.  
  49. #include <bits/stdc++.h>
  50. using namespace std;
  51.  
  52. #define ll long long
  53. #define endl '\n'
  54. #define fi first
  55. #define se second
  56. #define vall(a) (a).begin(), (a).end()
  57. #define sze(a) (int)a.size()
  58. #define pii pair<int, int>
  59.  
  60. #define pb push_back
  61. #define pf push_front
  62.  
  63.  
  64. const int mod = 1e9 + 7;
  65. const signed N = 5e5 + 5;
  66. const ll oo = 1e18;
  67.  
  68.  
  69. int n, k, pre[N];
  70. vector<pii> kd;
  71.  
  72. short d[N];
  73.  
  74. void output() {
  75. 	int p = 0, cur = 0;
  76. 	for (int i = 1; i <= n; ++i) {
  77. 		if (d[i] == 0) continue;
  78. 		if (cur == 0) p = i;
  79. 		cur += d[i];
  80. 		if (cur == 0) kd.pb(make_pair(p, i - 1));
  81. 	}
  82. 	pre[1] = 1;
  83. 	for (int i = 2; i <= n; ++i) {
  84. 		int l_, r_;
  85. 		for (pii pos : kd) {
  86. 			l_ = i - pos.fi;
  87. 			r_ = i - pos.se;
  88. 			if (r_ < 1 && l_ >= 1) {
  89. 				pre[i] += pre[l_] - pre[0];
  90. 				if (pre[i] < 0) pre[i] += mod;
  91. 				if (pre[i] >= mod) pre[i] -= mod;
  92. 			}
  93. 			if(l_ >= 1 && r_ >= 1) {
  94. 				pre[i] += pre[l_] - pre[r_ - 1];
  95. 				if (pre[i] < 0) pre[i] += mod;
  96. 				if (pre[i] >= mod) pre[i] -= mod;
  97.  
  98. 			}
  99. 		}
  100. 		if (i == n) continue;
  101.  
  102. 		pre[i] += pre[i - 1];
  103. 		if (pre[i] < 0) pre[i] += mod;
  104. 		if (pre[i] >= mod) pre[i] -= mod;
  105. 	}
  106. 	cout << pre[n];
  107.     return;
  108. }
  109.  
  110. void input() {
  111. 	cin >> n >> k;
  112. 	int l, r;
  113. 	for (int i = 1; i <= k; ++i) {
  114. 		cin >> l >> r;
  115. 		++d[l];
  116. 		--d[r + 1];
  117. 	}
  118.     output();
  119.     return;
  120. }
  121.  
  122. signed main () {
  123.     if(fopen("", "r")) {
  124.         freopen("", "r", stdin);
  125.         freopen("", "w", stdout);
  126.     }
  127.     ios_base::sync_with_stdio(false);
  128.     cin.tie(nullptr); cout.tie(nullptr);
  129.  
  130.     input();
  131.     return 0;
  132. }
  133.  
Success #stdin #stdout 0.01s 5284KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/B0BCUU
language:
C++14 (gcc 8.3)
created:
4 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!