Pagini recente » Cod sursa (job #3121805) | Cod sursa (job #7101) | Cod sursa (job #2061236) | Cod sursa (job #3125390) | Cod sursa (job #180194)
Cod sursa(job #180194)
#include <stdio.h>
#include <iostream>
#include <fstream>
using namespace std;
int s[100000],f[100000],a[100000],sol[100001];
int N;
int binary_search(int val)
{
int i, step;
for (step = 1; step < N; step <<= 1);
for (i = 0; step; step >>= 1)
if (i + step < N && f[a[i + step]] <= val)
i += step;
return i;
}
void quicksort (int a[], int lo, int hi)
{
int i=lo, j=hi, h;
int x=f[a[lo+rand()%(hi-lo+1)]];
do
{
while (f[a[i]]<x) i++;
while (f[a[j]]>x) j--;
if (i<=j)
{
h=a[i]; a[i]=a[j]; a[j]=h;
i++; j--;
}
} while (i<=j);
if (lo<j) quicksort(a, lo, j);
if (i<hi) quicksort(a, i, hi);
}
int main(void){
ifstream in("heavymetal.in" );
ofstream out("heavymetal.out");
int i,j,max = 0;
in >> N;
for (int i=0;i<N;i++){
in >> s[i] >> f[i];
a[i] = i;
}
quicksort(a,0,N-1);
for (int i=0;i<N;i++){
int find = binary_search(s[a[i]]);
if (find == 0 && f[a[0]] > s[a[i]]) find = -1;
int pr = sol[find+1];
while (find != i){
if (sol[find] > pr)
pr = sol[find];
find ++;
}
sol[i+1] = pr+1;
//cout << sol[i+1] << " ";
if (sol[i+1] > max) max = sol[i+1];
}
out << max;
in.close();
out.close();
return 0;
}