Cod sursa(job #734038)

Utilizator danalex97Dan H Alexandru danalex97 Data 13 aprilie 2012 14:12:35
Problema Stalpi Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.48 kb
#include <fstream>
#include <algorithm>
using namespace std;

#define MaxN 100000
#define oo MaxN*MaxN

#define one first
#define two second

#define X one.one
#define C one.two
#define S two.one
#define D two.two

#define PP pair < pair<int,int>,pair<int,int> >
#define aib(i) ( ( i^(i-1) ) & i )

typedef int AIB[MaxN+11];

PP A[MaxN+11];
int V[MaxN+11];
int N;

AIB Aib;

void update(int pl,int val)
{	
	for ( int i=pl;i<=N;i+=aib(i) )
		Aib[i]+=val; 
}

int seek(int x)
{   
	int rez=0; 
	for ( int i=x;i>0;i-=aib(i) )
		rez+=Aib[i];
	return rez;
}

int binfire(int sum)
{
	int st=1,dr=N,mid,x;
    
	while ( dr>st )
	{
        mid=(st+dr) /2;
        x=seek(mid);
        
		if ( x>sum )
			dr=mid-1; 
		else
			if ( x<sum )
				st=mid+1; 
			else 
				return mid;
	}
    
	return ( seek(st)==sum ) ? st : -1 ;
}

bool cmp(PP A,PP B)
{return ( A.X < B.X || ( A.X == B.X && A.X + A.D < B.X + B.D ) );}

int main(void)
{
	ifstream F("stalpi.in");
	ofstream G("stalpi.out");
	
	F>>N;
	for (int i=1;i<=N;++i)
		F>>A[i].X>>A[i].C>>A[i].S>>A[i].D;
	
	sort(A,A+N+1,cmp);
	for (int i=1;i<=N;++i) 
		V[i] = A[i].X + A[i].D;
	sort(V,V+N+1);
	
	for (int i=1;i<=N;++i)
		Aib[i]=oo;
	
	for (int i=1;i<=N;++i)
	{
		Aib[i]=A[i].S;
		int a=A[i].X-A[i].D;
		
		if( a > A[1].X )
			Aib[i] += seek ( binfire(a) ) ;
		update( binfire ( A[i].X + A[i].S + 1 ) , Aib[i] );
	}
	
	G<<seek( binfire (A[N].X + 1) );
	
	F.close();
	G.close();
}