Advertisement
Guest User

Untitled

a guest
Feb 19th, 2017
83
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.63 KB | None | 0 0
  1. #define _CRT_SECURE_NO_WARNINGS
  2. #include <vector>
  3. #include <map>
  4. #include <set>
  5. #include <complex>
  6. #include <ctime>
  7. #include <iostream>
  8. #include <cmath>
  9. #include <stack>
  10. #include <sstream>
  11. #include <stdio.h>
  12. #include <algorithm>
  13. #include <queue>
  14. #include <cstring>
  15. #include <cassert>
  16. #include <sstream>
  17.  
  18. const long double PI(acosl(-1.0));
  19. long double eps = 1e-9;
  20.  
  21. #define pb push_back
  22. #define mp(a,b) make_pair(a,b)
  23. #define all(x) x.begin(), x.end()
  24. #define sqr(x) ((x)*(x))
  25. #define F first
  26. #define S second
  27. #define inf (int)(1e9+7)
  28. #define infll (ll)(1e18+3)
  29. #define sz(x) ((int)x.size())
  30. #define bits(x) __builtin_popcount(x)
  31. #define bitsl(x) __builtin_popcountll(x)
  32. #define rep(i, a, b) for (int (i) = (a); i <= (b); ++(i))
  33. #define forn(i, n) rep(i, 0, n-1)
  34.  
  35. using namespace std;
  36. typedef unsigned long long ull;
  37. typedef long long ll;
  38. typedef long double ld;
  39. typedef vector <ll > vll;
  40. typedef vector<int> vi;
  41. typedef pair < ll, ll > pll;
  42. typedef pair < int, int > pii;
  43. typedef vector<vi> vii;
  44. typedef int huint;
  45.  
  46. using namespace std;
  47.  
  48. const int N = 500000;
  49.  
  50.  
  51. vector<pii> p;
  52. map<pii, char> mp;
  53.  
  54. int main() {
  55.  
  56. std::ios_base::sync_with_stdio(false);
  57. cin.tie(0); cout.tie(0);
  58.  
  59. freopen("library.in", "r", stdin);
  60. freopen("library.out", "w", stdout);
  61.  
  62.  
  63. int n;
  64. cin >> n;
  65. for (int i(0); i < n; i++)
  66. {
  67. int x, y, z;
  68. cin >> x >> y >> z;
  69. x += z;
  70. if (x > y)
  71. {
  72. cout << "NO";
  73. return 0;
  74. }
  75. p.pb({ y,x });
  76. }
  77. sort(all(p));
  78.  
  79. for (int i(0); i < n; i++)
  80. {
  81. pii a = p[i];
  82. if (mp.count({ a.S, a.S }) == 1)
  83. {
  84. if (a.S == a.F)
  85. {
  86. cout << "NO";
  87. return 0;
  88. }
  89. auto x = mp.find({ a.S, a.S });
  90. x++;
  91. if (x != mp.end() && x->F.F == a.S + 1)
  92. {
  93. if (x->first.S >= a.F)
  94. {
  95. cout << "NO";
  96. return 0;
  97. }
  98. int l = x->first.F;
  99. int r = x->first.S + 1;
  100. mp.erase(x);
  101. mp[{l, r}] = 1;
  102.  
  103. }
  104. else
  105. {
  106. mp.erase({ a.S, a.S });
  107. mp[{a.S, a.S + 1}] = 1;
  108. }
  109. continue;
  110. }
  111. else mp[{a.S, a.S}] = 1;
  112. auto x = mp.find({ a.S, a.S });
  113. auto z = mp.find({ a.S, a.S });
  114. bool fl = false;
  115. if(x == mp.begin()) fl = 1;
  116. x++;
  117. if (x != mp.end())
  118. {
  119. if (x->first.F > a.S)
  120. {
  121. x--;
  122. x--;
  123. }
  124. else
  125. fl = 0;
  126. }
  127. else
  128. {
  129. x--;
  130. x--;
  131. }
  132.  
  133. while (1 && !fl)
  134. {
  135.  
  136. if (x == mp.end() )
  137. {
  138. cout << "b\n";
  139. break;
  140. }
  141. if (x->first.F > a.S)
  142. break;
  143. if (x->first.F <= a.S)
  144. {
  145. if (x->first.S >= a.F)
  146. {
  147. cout << "NO";
  148. return 0;
  149. }
  150. if (x->first.S >= a.S - 1)
  151. {
  152. int l = x->first.F;
  153. int r = x->first.S + 1;
  154. mp.erase(x);
  155. mp.erase(z);
  156. mp[{l, r}] = 1;
  157. break;
  158. }
  159. break;
  160. }
  161. }
  162. }
  163.  
  164. cout << "YES";
  165.  
  166. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement