Advertisement
Guest User

Untitled

a guest
May 22nd, 2017
56
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1.  
  2. #include <stdio.h>
  3. #include <string.h>
  4. #include <stdlib.h>
  5. #include <math.h>
  6.  
  7. #include <string>
  8. #include <vector>
  9. #include <stack>
  10. #include <queue>
  11. #include <map>
  12. #include <set>
  13. #include <algorithm>
  14. using namespace std;
  15.  
  16. struct ev
  17. {
  18.     int tipo; //1=sobe 2=desce
  19.     long long h, x;
  20.  
  21.     bool operator<(const ev& e) const
  22.     {
  23.         if(x != e.x) return x<e.x;
  24.  
  25.         if(tipo == 1 && e.tipo == 1) return h < e.h;
  26.         if(tipo == 2 && e.tipo == 2) return h > e.h;
  27.  
  28.         return (tipo == 2);
  29.     }
  30.  
  31.     ev(int tipo, long long x, long long h): x(x), h(h), tipo(tipo) {}
  32.     ev(){}
  33. };
  34.  
  35.  
  36. #define MAX 80400
  37.  
  38. ev evs[MAX];
  39.  
  40. multiset<long long, greater<long long> > heap;
  41.  
  42. int main(void)
  43. {
  44.     int n, i, j;
  45.     long long res;
  46.     long long a, b, h;
  47.  
  48.     scanf("%d", &n);
  49.     for(i=0; i<n; i++)
  50.     {
  51.         scanf("%lld %lld %lld", &a, &b, &h);
  52.        
  53.         evs[2*i] = ev(1, a, h);
  54.         evs[2*i+1] = ev(2, b, h);
  55.     }
  56.  
  57.     sort(evs, evs + 2*n);
  58.  
  59.     res = 0;
  60.     long long ultx = 0, ulth = 0;
  61.     //for(set<ev>::iterator it = evs.begin(); it != evs.end(); ++it)
  62.     for(ev* it = evs; it != (evs+2*n); it++)
  63.     {
  64.         if(it->tipo == 1)
  65.         {
  66.             res += (it->x - ultx) * (ulth);
  67.             heap.insert(it->h);
  68.  
  69.             //printf("sobe x=%d h=%d res=%d\n", it->x, it->h, res);
  70.         }
  71.         else
  72.         {
  73.             res += (it->x - ultx) * (ulth);
  74.             heap.erase(heap.find(it->h));
  75.    
  76.             //printf("desce x=%d h=%d res=%d\n", it->x, it->h, res);
  77.         }
  78.  
  79.         ultx = it->x;
  80.         ulth = *heap.begin();
  81.     }
  82.  
  83.     printf("%Ld\n", res);
  84.  
  85.     return 0;
  86. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement