Cod sursa(job #1897646)

Utilizator valentin50517Vozian Valentin valentin50517 Data 1 martie 2017 16:51:00
Problema Heavy metal Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.88 kb
#include <bits/stdc++.h>
#define y second
#define x first
typedef long long ll;
using namespace std;
ll N,D[100100],I[100100];
pair<int,int> A[100100];
int caut(int y){
	int st=1,dr=N;
	while(st<dr-3){
		int mid = (st+dr)/2;
		if(y<=A[mid].x) dr = mid; 
		else st = mid+1;
	}
	for(;st<=dr;st++) if(A[st].x>=y) return st;
	return -1; 
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);
    ifstream cin("heavymetal.in");
    ofstream cout("heavymetal.out");
    cin >> N;
    for(int i = 1,x,y;i<=N;i++){
        cin >> x >> y;
        A[i] = make_pair(x,y);
    }
    sort(A+1,A+1+N);
    //for(int i = 1;i<=N;i++) cout << A[i].x  << ' ' << A[i].y << '\n';
    for(int i = 1;i<=N;i++){
		D[i] = A[i].y - A[i].x + D[I[i]];
		D[i] = max(D[i],D[i-1]);
		int up = caut(A[i].y); 
        if(up > 0) I[up]=i;
        //for(int j = 1;j<=N;j++) cout << D[j] << "\n "[j<N];
    }
    cout << D[N];
}