Pagini recente » Cod sursa (job #1327775) | Cod sursa (job #1586199) | Cod sursa (job #2761685) | Cod sursa (job #1450811) | Cod sursa (job #350355)
Cod sursa(job #350355)
#include <fstream.h>
struct el{ int d,a; } v[100001];
int N,range,L;
int mergesort(int,int);
void merge(int,int,int);
int search_low(int);
int search_top(int);
int get_max(int,int);
int main()
{
int i,a,z,S=0;
ifstream in("lupu.in");
in>>N>>range>>L;
for(i=1;i<=N;i++)
in>>v[i].d>>v[i].a;
in.close();
mergesort(1,N);
do
{
if(range+1-L<0) a=search_low(0);
else a=search_low(range+1-L);
z=search_top(range);
S+=get_max(a,z);
range-=L; N=a-1;
}while(N>0);
ofstream out("lupu.out");
out<<S;
out.close();
return 0;
}
int mergesort(int first,int last)
{
int mid=(first+last)/2;
if(first<last)
{
mergesort(first,mid);
mergesort(mid+1,last);
merge(first,mid,last);
}
return 0;
}
void merge(int first,int mid,int last)
{
int i=first,j=mid+1,k=first;
el c[100001];
while(i<=mid && j<=last)
{
if(v[i].d<=v[j].d) c[k++]=v[i++];
else c[k++]=v[j++];
}
while(i<=mid) c[k++]=v[i++];
while(j<=last) c[k++]=v[j++];
for(i=first;i<k;i++)
v[i]=c[i];
}
int search_low(int key)
{
int first=1,mid,last=N;
while(first<=last)
{
mid=(first+last)/2;
if(v[mid].d>key) last=mid-1;
if(v[mid].d<key)
if(v[mid+1].d>=key) return mid+1;
else first=mid+1;
if(v[mid].d==key)
{
mid--;
while(mid>1 && v[mid].d==key) mid--;
return mid+1;
}
}
}
int search_top(int key)
{
int first=1,mid,last=N;
while(first<=last)
{
mid=(first+last)/2;
if(v[mid].d>key)
if(v[mid-1].d<=key) return mid-1;
else last=mid-1;
if(v[mid].d<key) first=mid+1;
if(v[mid].d==key)
{
mid++;
while(mid<=N && v[mid].d==key) mid++;
return mid-1;
}
}
}
int get_max(int first,int last)
{
int i,max=0;
for(i=first;i<=last;i++)
if(v[i].a>max) max=v[i].a;
return max;
}