Cod sursa(job #1040208)

Utilizator andreiblaj17Andrei Blaj andreiblaj17 Data 24 noiembrie 2013 09:58:30
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100001

using namespace std;

int n,x,i,j,mid,k,y,maxim,minim,num;
int c[nmax],d[nmax];
vector <int> a,b;

int merge(int lo, int hi){
    mid=(lo+hi)/2;
    
    i=lo;
    j=mid+1;
    k=lo;
    
    while (i<=mid && j<=hi){
        if (a[i]<=a[j]){
            c[k]=a[i];
            d[k]=b[i];
            i++;
        } else {
            c[k]=a[j];
            d[k]=b[j];
            j++;
        }
        k++;
    }
    
    while (i<=mid)
        c[k]=a[i], d[k]=b[i], i++, k++;
    
    while (j<=hi)
        c[k]=a[j], d[k]=b[j], j++, k++;
    
    for (i=lo; i<=hi; i++)
        a[i]=c[i], b[i]=d[i];
    
    return 0;
    
}

int mergesort(int lo, int hi){
    
    if (lo==hi) return 1;
    
    int mid;
    
    mid=(lo+hi)/2;
    
    mergesort(lo, mid);
    mergesort(mid+1, hi);
    
    merge(lo, hi);
    
    return 0;
}

int main(){
    
    ifstream in("heavymetal.in");
    ofstream out("heavymetal.out");
    
    in >> n;
    
    for (i=1; i<=n; i++){
        in >> x >> y;
        a.push_back(x);
        b.push_back(y);
    }
    
    mergesort(0, n-1);
    
    maxim=0;
    minim=0;
    num=0;
    
    for (i=0; i<n; i++)
        if (a[i]>=maxim){
            
            num+=maxim-minim;
            
            maxim=b[i];
            minim=a[i];
            
        } else maxim=max(maxim, b[i]);
    
    num+=maxim-minim;
    
    out << num << "\n";
    
    return 0;
}