fork download
copy 
  1. #include<iostream>
  2. #include<stdio.h>
  3. #include<vector>
  4. #include<algorithm>
  5.  
  6. using namespace std ;
  7. struct data {
  8.     long long left , right , height ;
  9.     data() {}
  10.     data(long long _left , long long _right, long long _height ) {
  11.         left = _left , right = _right , height = _height ;
  12.     }
  13. };
  14. data arr[40000+5] ;
  15. long long Tree[160000+5] ;
  16. vector<long long>V ;
  17. long long h ;
  18. int l , r ;
  19. void propagate( int nd , int i , int j ) {
  20.     if( j-i > 1 && Tree[nd] > 0 ) {
  21.         Tree[nd<<1] = h ;
  22.         Tree[(nd<<1)+1] = h ;
  23.         Tree[nd] = 0; ;
  24.     }
  25. }
  26. void build( int nd , int st , int en ) {
  27.     Tree[nd] = 0/*data(st,en,0)*/ ;
  28.     if( st+1 == en )return ;
  29.     build( (nd<<1) , st , (st+en)>>1 );
  30.     build( (nd<<1)+1 , (st+en)>>1 , en );
  31. }
  32. void update( int nd , int st , int en ) {
  33.     propagate(nd,st,en) ;
  34.     if( st == en ) return  ;
  35.     if( st > r || en < l ) return ;
  36.     if( st>=l && en <= r ) {
  37.         Tree[nd] = max( Tree[nd] , h ) ;
  38.         return ;
  39.     }
  40.     if( st+1 == en ) return  ;
  41.     update( (nd<<1) , st , (st+en)>>1 );
  42.     update( (nd<<1)+1 , (st+en)>>1 , en );
  43. }
  44. long long query( int nd , int st , int en ) {
  45.     propagate(nd,st,en) ;
  46.     if( st == en ) return 0 ;
  47.     if( en-st == 1 ) {
  48.         long long ans = (V[en]-V[st])*Tree[nd] ;
  49.         return ans ;
  50.     }
  51.  
  52.     return query( (nd<<1) , st , (st+en)>>1 )
  53.            +query( (nd<<1)+1 , (st+en)>>1 , en );
  54. }
  55. int main() {
  56.  
  57.     int n ;
  58.     scanf("%lld",&n);
  59.     for(int i = 0; i < n ; i++ ) {
  60.         scanf("%lld%lld%lld",&arr[i].left,&arr[i].right,&arr[i].height) ;
  61.         V.push_back(arr[i].left) ;
  62.         V.push_back(arr[i].right) ;
  63.     }
  64.     sort( V.begin() , V.end() ) ;
  65.     V.erase(unique(V.begin(),V.end()),V.end()) ;
  66.     build(1,0,V.size()-1);
  67.     for(int i = 0 ; i < n ; i++ ) {
  68.         l = upper_bound(V.begin(),V.end(),arr[i].left) - V.begin();
  69.         r = upper_bound(V.begin(),V.end(),arr[i].right) - V.begin();
  70.         h = arr[i].height ;
  71.         l--,r--;
  72.         update( 1 , 0 , V.size()-1 ) ;
  73.     }
  74.     cout << query( 1 , 0 , V.size()-1) << "\n" ;
  75.     return 0 ;
  76. }
  77.  
Success #stdin #stdout 0s 5468KB
comments (?)
stdin
copy 
4
2 5 1
9 10 4
6 8 2
4 6 3
stdout
copy 
16
https://ideone.com/RF1JfE
language:
C++14 (gcc 8.3)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!