Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <stdio.h>
- #include <string.h>
- #include <stdlib.h>
- #include <math.h>
- #include <string>
- #include <vector>
- #include <stack>
- #include <queue>
- #include <map>
- #include <set>
- #include <algorithm>
- using namespace std;
- struct ev
- {
- int tipo; //1=sobe 2=desce
- long long h, x;
- bool operator<(const ev& e) const
- {
- if(x != e.x) return x<e.x;
- if(tipo == 1 && e.tipo == 1) return h < e.h;
- if(tipo == 2 && e.tipo == 2) return h > e.h;
- return (tipo == 2);
- }
- ev(int tipo, long long x, long long h): x(x), h(h), tipo(tipo) {}
- ev(){}
- };
- #define MAX 80400
- ev evs[MAX];
- multiset<long long, greater<long long> > heap;
- int main(void)
- {
- int n, i, j;
- long long res;
- long long a, b, h;
- scanf("%d", &n);
- for(i=0; i<n; i++)
- {
- scanf("%lld %lld %lld", &a, &b, &h);
- evs[2*i] = ev(1, a, h);
- evs[2*i+1] = ev(2, b, h);
- }
- sort(evs, evs + 2*n);
- res = 0;
- long long ultx = 0, ulth = 0;
- //for(set<ev>::iterator it = evs.begin(); it != evs.end(); ++it)
- for(ev* it = evs; it != (evs+2*n); it++)
- {
- if(it->tipo == 1)
- {
- res += (it->x - ultx) * (ulth);
- heap.insert(it->h);
- //printf("sobe x=%d h=%d res=%d\n", it->x, it->h, res);
- }
- else
- {
- res += (it->x - ultx) * (ulth);
- heap.erase(heap.find(it->h));
- //printf("desce x=%d h=%d res=%d\n", it->x, it->h, res);
- }
- ultx = it->x;
- ulth = *heap.begin();
- }
- printf("%Ld\n", res);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement