fork(7) download
copy 
  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
comments (?)
stdin
copy 
8 7
0 3
2 5
5 8
1 3
3 6
4 6
0 2
0 0
stdout
copy 
4
https://ideone.com/4f8gLg
spoj MHLAR10
language:
C++ 4.3.2 (gcc-4.3.2)
created:
10 years 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!