fork(7) download
  1. /*
  2. ID: tiendao1
  3. LANG: C++
  4. TASK: game1
  5. */
  6.  
  7. //#include <bits/stdc++.h>
  8. #include<iostream>
  9. #include<cstdio>
  10. #include <sstream>
  11. #include<string>
  12. #include<cstring>
  13. #include<map>
  14. #include<set>
  15. #include<deque>
  16. #include<queue>
  17. #include<stack>
  18. #include<vector>
  19. #include<algorithm>
  20. #include<cstdlib>
  21. #include<bitset>
  22. #include<climits>
  23. #include <list>
  24. #include <functional>
  25. #include <cmath>
  26. #include <ctime>
  27. #include <utility>
  28.  
  29. using namespace std;
  30. typedef long long ll;
  31. typedef unsigned long long ull;
  32. #define inf 1e9
  33. #define linf 1e18
  34. #define EPS 1e-5
  35. #define PI acos(-1)
  36. #define pii pair<int,int>
  37. #define fi first
  38. #define se second
  39. #define ALL(x) (x).begin(), (x).end()
  40. #define ms(x,val) memset(x, val, sizeof(x))
  41. #define pb(x) push_back(x)
  42. #define make_unique(x) sort(ALL(x)) ; x.erase( unique(ALL(x)), x.end()) ;
  43.  
  44. const int bfsz = 1 << 16;
  45. char bf[bfsz + 5];
  46. int rsz = 0;
  47. int ptr = 0;
  48. char gc()
  49. {
  50. if (rsz <= 0)
  51. {
  52. ptr = 0;
  53. rsz = fread(bf, 1, bfsz, stdin);
  54. if (rsz <= 0) return EOF;
  55. } --rsz;
  56. return bf[ptr++];
  57. }
  58. void ga(char &c)
  59. {
  60. c = EOF;
  61. while (!isalpha(c)) c = gc();
  62. }
  63. int gs(char s[])
  64. {
  65. int l = 0;
  66. char c = gc();
  67. while (isspace(c)) c = gc();
  68. while (c != EOF && !isspace(c))
  69. {
  70. s[l++] = c;
  71. c = gc();
  72. }
  73. s[l] = '\0';
  74. return l;
  75. }
  76. template<class T> bool gi(T &v)
  77. {
  78. v = 0;
  79. char c = gc();
  80. while (c != EOF && c != '-' && !isdigit(c)) c = gc();
  81. if (c == EOF) return false;
  82. bool neg = c == '-';
  83. if (neg) c = gc();
  84. while (isdigit(c))
  85. {
  86. v = v * 10 + c - '0';
  87. c = gc();
  88. }
  89. if (neg) v = -v;
  90. return true;
  91. }
  92.  
  93. long long gcd(long long x, long long y)
  94. {
  95. return y == 0 ? x : gcd(y, x % y);
  96. }
  97. int toInt(char xx)
  98. {
  99. return xx - '0';
  100. }
  101.  
  102. int exitInput = 0;
  103. int ntest = 1, itest = 1 ;
  104.  
  105. void read() ;
  106. void solve() ;
  107.  
  108. int main()
  109. {
  110.  
  111. #ifndef ONLINE_JUDGE
  112. //freopen("game1.in","r",stdin) ;freopen("game1.out", "w", stdout);
  113. freopen("gentest.txt", "r", stdin);
  114. freopen("output.txt", "w", stdout);
  115. clock_t t1, t2 ;
  116. //t1 = clock() ;
  117. #endif
  118. ios_base::sync_with_stdio(0) ;
  119.  
  120. //cin >> ntest;
  121. //scanf("%d",&ntest) ;
  122. //gi(ntest) ;
  123.  
  124. for (itest = 1; itest <= ntest ; ++itest)
  125. for (itest = 1; ; ++itest)
  126. {
  127. read();
  128. if (exitInput)
  129. {
  130. break;
  131. }
  132. if(itest > 1)
  133. {
  134. //printf("\n") ;
  135. //cout << endl ;
  136. }
  137. //cout << "Case " << itest << ": ";
  138. //printf("Case #%d\n",itest) ;
  139. solve();
  140.  
  141. }
  142.  
  143. #ifndef ONLINE_JUDGE
  144. //t2 = clock() ;printf("\nRunning time : %.6f\n",((float)t2 - (float)t1) / CLOCKS_PER_SEC) ;
  145. #endif
  146. return 0;
  147. }
  148.  
  149.  
  150. /*** IMPLEMENTATION ***/
  151. const int dx[4] = { -1, 1, -2, 2 };
  152. const int dy[4] = { 2, -2, -1, 1 };
  153. const ll Mod = 1e8;
  154. const int maxn = 100 + 5 ;
  155.  
  156. int n, m ;
  157. pii a[maxn] ;
  158. int f[2*maxn][2*maxn] ;
  159. vector<int> rrh ;
  160. int hasZero, hasN ;
  161.  
  162. int dp(int L, int R)
  163. {
  164. int &ref = f[L][R] ;
  165. if(ref != -1)
  166. {
  167. return ref ;
  168. }
  169. ref = 0 ;
  170. int i, lo, hi ;
  171.  
  172. for(i = 0; i < m; ++i)
  173. {
  174. lo = a[i].fi ; hi = a[i].se ;
  175.  
  176. if(lo < L && L <= hi && hi < R)
  177. {
  178. if(lo == 1)
  179. {
  180. ref += 1 ;
  181. }
  182. else
  183. {
  184. ref += dp(lo,min(hi,L)) ;
  185. }
  186. }
  187. ref %= Mod ;
  188. }
  189. return ref ;
  190. }
  191.  
  192. void read()
  193. {
  194. #define endread { exitInput = 1 ; return ; }
  195. rrh.clear();
  196. cin >> n >> m ; if(n + m == 0) endread ;
  197.  
  198. hasZero = hasN = 0 ;
  199.  
  200. rrh.pb(n);
  201. for(int i = 0; i < m; ++i)
  202. {
  203. cin >> a[i].fi >> a[i].se ;
  204. if(a[i].fi == 0) hasZero = 1 ;
  205. if(a[i].se == n) hasN = 1 ;
  206.  
  207. rrh.pb(a[i].fi); rrh.pb(a[i].se);
  208. }
  209. make_unique(rrh);
  210. n = 1 + lower_bound(ALL(rrh),n)-rrh.begin();
  211. for(int i = 0; i < m; ++i)
  212. {
  213. a[i].fi = 1 + lower_bound(ALL(rrh),a[i].fi)-rrh.begin();
  214. a[i].se = 1 + lower_bound(ALL(rrh),a[i].se)-rrh.begin();
  215. }
  216.  
  217. // printf("n = %d\n",n);
  218. // for(int i = 0; i < m; ++i)
  219. // {
  220. // printf("i = %d, fi = %d, se = %d\n",i,a[i].fi,a[i].se);
  221. // }
  222.  
  223. }
  224.  
  225. void solve()
  226. {
  227. if(!hasZero || !hasN)
  228. {
  229. puts("0");
  230. return ;
  231. }
  232. ms(f,-1) ;
  233. int res = 0, i, lo, hi ;
  234. for(i = 0; i < m; ++i)
  235. {
  236. lo = a[i].fi ; hi = a[i].se ;
  237. if(lo == 1)
  238. {
  239. f[lo][hi] = 1;
  240. }
  241. }
  242. for(i = 0; i < m; ++i)
  243. {
  244. lo = a[i].fi ; hi = a[i].se ;
  245. if(hi == n)
  246. {
  247. res += dp(lo,hi) ;
  248. res %= Mod ;
  249. }
  250. }
  251. printf("%d\n",res) ;
  252. }
  253.  
Success #stdin #stdout 0s 3064KB
stdin
8 7
0 3
2 5
5 8
1 3
3 6
4 6
0 2
0 0
stdout
4