Pagini recente » Statistici paun darius alexandru (pokermon2005) | Cod sursa (job #2143869) | Cod sursa (job #2490314) | Cod sursa (job #1799806) | Cod sursa (job #734038)
Cod sursa(job #734038)
#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();
}