prestige

Untitled

Jan 21st, 2014
159
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.15 KB | None | 0 0
  1. #include <algorithm>
  2. #include <bitset>
  3. #include <cassert>
  4. #include <cmath>
  5. #include <cstdio>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <iostream>
  9. #include <list>
  10. #include <map>
  11. #include <queue>
  12. #include <set>
  13. #include <string>
  14. #include <sstream>
  15. #include <vector>
  16. #include <complex>
  17. #include <ctime>
  18. #include <stack>
  19.  
  20. using namespace std;
  21.  
  22. typedef long long ll;
  23. typedef unsigned long long ull;
  24. typedef vector<int> VI;
  25. typedef vector< VI > VVI;
  26. typedef pair<int, int> PII;
  27. typedef vector<PII> VPII;
  28.  
  29. #define REP(i, n) for(int i = 0; i < (n); ++i)
  30. #define RREP(i, n) for(int i = (n) - 1; i >= 0; --i)
  31. #define FOR(i, x, y) for(int i = (x); i <= (y); ++i)
  32. #define RFOR(i, x, y) for(int i = (x); i >= (y); --i)
  33. #define SZ(a) (int)(a).size()
  34. #define ALL(a) (a).begin(),(a).end()
  35. #define SORT(a) sort(ALL(a))
  36. #define CLEAR(x) memset(x, 0, sizeof x);
  37. #define COPY(FROM, TO) memcpy(TO, FROM, sizeof TO);
  38. #define UNIQUE(c) SORT(c),(c).resize(unique(ALL(c))-(c).begin())
  39. #define pb push_back
  40. #define mk make_pair
  41. #define sqr(x) ((x)*(x))
  42. #define X first
  43. #define Y second
  44. const long double pi=acos(-1.0);
  45. const double EPS = 1E-9;
  46. const int INF = (1e+9);
  47. const int NMAX = 31625;
  48. const int MOD = 1743;
  49.  
  50. int n, k;
  51. vector<pair<PII, int> > arr;
  52. struct aaa{
  53. int l, r, n;
  54. aaa (pair<PII, int> val_) {
  55. l = val_.X.X;
  56. r = val_.X.Y;
  57. n = val_.Y;
  58. }
  59. bool operator< (const aaa& rhs) const {
  60. return r <= rhs.r;
  61. }
  62. };
  63. set<aaa> st;
  64. int main () {
  65. freopen ("ancient.in", "r", stdin);
  66. freopen ("ancient.out", "w", stdout);
  67. cin >> n;
  68. arr.resize(n);
  69. REP (i, n) {
  70. cin >> arr[i].X.X >> arr[i].X.Y;
  71. arr[i].Y = i;
  72. }
  73. SORT(arr);
  74. int minn = INF;
  75. int s1 = -1, s2 = -1;
  76. REP (i, n) {
  77. if (!st.empty()) {
  78. aaa top(*st.begin());
  79. int intersect = min(top.r, arr[i].X.Y) - arr[i].X.X;
  80. if (intersect <= 0)
  81. st.erase(st.begin());
  82. else if (minn > intersect) {
  83. minn = intersect;
  84. s1 = arr[i].Y, s2 = top.n;
  85. }
  86. }
  87. st.insert (aaa(arr[i]));
  88. }
  89. if (s1 < 0)
  90. cout << 0;
  91. else
  92. cout << s1 + 1 << " " << s2 + 1;
  93. }
  94. /*
  95. 6
  96. 1 3 5 7 11 13
  97. 5
  98. */
Advertisement
Add Comment
Please, Sign In to add comment