Pagini recente » Cod sursa (job #652658) | Cod sursa (job #1116216) | Cod sursa (job #1494407) | Cod sursa (job #2560423) | Cod sursa (job #2912742)
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("lupu.in");
ofstream fout("lupu.out");
int n,x,l,l2,suma;
int r[17][100005];
int e[100005];
struct numar{
int d;
int val;
}v[100005];
void process()
{
r[0][1]=v[1].val;
for(int i=2;i<=n;i++)
{
r[0][i]=v[i].val;
e[i] = 1+e[i/2];
}
for(int p=1;(1<<p)<=n;p++)
{
for(int i=1;i<=n;i++)
{
r[p][i]=r[p-1][i];
int j = i + (1<<(p-1));
if(j<=n && r[p][i]<r[p-1][j])
r[p][i]=r[p-1][j];
}
}
}
int cmp(numar a,numar b)
{
if(a.d != b.d)
return a.d<b.d;
return a.val<b.val;
}
int b_search_d()
{
int st=1;int dr=n;
while(st<=dr)
{
int mid=(st+dr)/2;
if(v[mid].d+l2>x)
{
dr=mid-1;
}
else{
st=mid+1;
}
}
return st;
}
int main()
{
fin>>n>>x>>l;
l2=l;
for(int i=1;i<=n;i++)
fin>>v[i].d>>v[i].val;
sort(v+1,v+n+1,cmp);
process();
int poz = -1;
while(1)
{
int maxim = -1;
poz = b_search_d();
for(int i=poz;i<=n;i++)
{
maxim=max(maxim,v[i].val);
}
int E = e[n-poz+1];
int len = (1<<E);
suma+=max(r[E][poz],r[E][n+1-len]);
n=poz-1;
l2+=l;
if(v[1].d+l2-l>x)
break;
}
fout<<suma;
}
/*
0 7
1 13
3 16
3 16
4 3
4 10
4 14
4 18
5 16
6 7
16 18 13 7
*/