Guest User

Untitled

a guest
Apr 19th, 2016
315
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 2.10 KB | None | 0 0
  1. /*
  2. ID: xildar91
  3. PROG: humble
  4. LANG: C++11
  5. */
  6. #include <bits/stdc++.h>
  7. using namespace std;
  8. typedef long long ll;
  9. typedef unsigned long long ull;
  10. typedef vector<int> vi;
  11. typedef vector<ll> vll;
  12. int inf_int=2e9;
  13. ll inf_ll=2e18;
  14. typedef pair<int,int> pii;
  15. #define pb push_back
  16. const double pi=3.1415926535898;
  17. #define dout if(debug) cout
  18. #define fi first
  19. #define se second
  20. #define sp setprecision
  21. #define sz size()
  22.  
  23. #define x1 gfgs
  24. #define y1 asd
  25. #define rank asdsad
  26. bool debug=0;
  27. const int maxn=1e5+7;
  28.  
  29. void solve()
  30. {
  31. int n;
  32. cin >> n;
  33. ll x1[n],y1[n],x2[n],y2[n];;
  34. vector<pair<pair<ll,ll> ,ll> >a;
  35. for(int i=0;i<n;i++)
  36. {
  37. cin >> x1[i]>>y2[i]>>x2[i]>>y1[i];
  38. a.pb({{x1[i],0},i});
  39. a.pb({{x2[i],1},i});
  40. }
  41. sort(a.begin(),a.end());
  42. ll ans=0;
  43. set<pair<pii,int> > s;
  44. ll prev;
  45. for(int i=0;i<a.sz;i++)
  46. {
  47. if(!i)
  48. {
  49. int in=a[i].se;
  50. s.insert({{y1[in],y2[in]},in});
  51. prev=a[i].fi.fi;
  52. }
  53. else
  54. {
  55. ll dis=a[i].fi.fi-prev;
  56. ll mn=-inf_ll;
  57. for(auto x:s)
  58. {
  59. mn=max(mn,(ll)x.fi.fi);
  60. ll val=max((ll)0,(x.fi.se-mn)*dis);
  61. ans+=val;
  62. mn=max(mn,(ll)x.fi.se);
  63.  
  64. }
  65. if(a[i].fi.se==1)
  66. {
  67. int in=a[i].se;
  68. s.erase({{y1[in],y2[in]},in});
  69. }
  70. else
  71. {
  72. int in=a[i].se;
  73. s.insert({{y1[in],y2[in]},in});
  74. }
  75. prev=a[i].fi.fi;
  76. }
  77. }
  78. cout << ans;
  79.  
  80.  
  81.  
  82. }
  83.  
  84.  
  85.  
  86.  
  87.  
  88.  
  89. #define FILE "B-large"
  90. int main()
  91. {
  92.  
  93. // freopen("input.txt","r",stdin);
  94. // freopen("output.txt","w",stdout);
  95.  
  96. // freopen(FILE".in","r",stdin);
  97. // freopen(FILE".out","w",stdout);
  98. if(!debug)
  99. {
  100. ios_base::sync_with_stdio(0);
  101. cin.tie(0);
  102. cout.tie(0);
  103. }
  104. int t=1;
  105. while(t--)
  106. solve();
  107. return 0;
  108. }
Advertisement
Add Comment
Please, Sign In to add comment