fork download
  1. #include <cstring>
  2. #include <cmath>
  3. #include <algorithm>
  4. #include <cstdlib>
  5. #include <cstdio>
  6. #include <iostream>
  7. #include <fstream>
  8. #include <queue>
  9.  
  10. #define rep(i, l, r) for(int i = l; i <= r; i++)
  11. #define down(i, l, r) for(int i = l; i >= r; i--)
  12. #define MS 234567
  13. #define MAX 1037471823
  14.  
  15. using namespace std;
  16.  
  17. int n, am, as, x, y, a, b, k[MS], t[MS], d[MS], q;
  18.  
  19. void Build(int o, int l, int r)
  20. {
  21. if (l != r)
  22. {
  23. Build(o*2, l, (l+r)/2); Build(o*2+1, (l+r)/2+1, r);
  24. k[o] = max(k[o*2], k[o*2+1]);
  25. }
  26. else k[o] = d[l];
  27. }
  28.  
  29. void Q(int o, int l, int r)
  30. {
  31. if (l == r && (x >= t[l] || t[r] >= y)) return;
  32. if (x < t[l] && t[r] < y) { as += r-l+1; am = max(am, k[o]); return; }
  33. if (x <= t[(l+r)/2]) Q(o*2, l, (l+r)/2);
  34. if (y > t[(l+r)/2]) Q(o*2+1, (l+r)/2+1, r);
  35. }
  36.  
  37. int QP(int x)
  38. {
  39. int l = 1, r = n;
  40. while (l != r)
  41. {
  42. if (x <= t[(l+r)/2]) r = (l+r)/2; else l = (l+r)/2+1;
  43. }
  44. if (x != t[l]) return 0; else return l;
  45. }
  46.  
  47. int main()
  48. {
  49. scanf("%d", &n);
  50. rep(i, 1, n) scanf("%d%d", &t[i], &d[i]); Build(1, 1, n);
  51. scanf("%d", &q);
  52. rep(i, 1, q)
  53. {
  54. scanf("%d%d", &x, &y);
  55. if (x > y) { printf("false\n"); continue; }
  56. if (x == y) { printf("maybe\n"); continue; }
  57. as = am = 0; Q(1, 1, n); a = QP(x); b = QP(y);
  58. if (a != 0 && b != 0 && d[a] >= d[b] && am < d[b] && as == y-x-1) printf("true\n");
  59. else if ((a != 0 && b != 0 && d[a] < d[b]) || (b != 0 && am >= d[b]) || (a != 0 && d[a] <= am)) printf("false\n");
  60. else printf("maybe\n");
  61. }
  62. return 0;
  63. }
Success #stdin #stdout 0s 6048KB
stdin
6
2002 4920
2003 5901
2004 2832
2005 3890
2007 5609
2008 3024
5
2002 2005
2003 2005
2002 2007
2003 2007
2005 2008
stdout
false
true
false
maybe
false