Pagini recente » Istoria paginii runda/124475824691316/clasament | Cod sursa (job #2777038) | Cod sursa (job #789494) | Istoria paginii runda/34554e/clasament | Cod sursa (job #1735298)
#include <iostream>
#include<fstream>
#include<algorithm>
using namespace std;
struct node
{
int value,poz;
}arb[400005];
struct oaie
{
int t,c;
}v[100005];
bool comp(oaie a,oaie b)
{
return a.t<b.t;
}
int val,pozitie,n,i,j,st,step,mx,x,l,d,a;
long long sum;
void update(int nod,int l,int r)
{
if(l==r)
{
arb[nod].value=val;
arb[nod].poz=l;
return;
}
int m=(l+r)/2;
if(pozitie<=m) update(2*nod,l,m);
else update(2*nod+1,m+1,r);
arb[nod].value=max(arb[2*nod].value,arb[2*nod+1].value);
if(arb[nod].value==arb[2*nod].value) arb[nod].poz=arb[2*nod].poz;
else arb[nod].poz=arb[2*nod+1].poz;
}
void query(int nod,int l,int r)
{
if(st<=l)
{
if(arb[nod].value>mx)
{
mx=arb[nod].value;
pozitie=arb[nod].poz;
}
return;
}
int m=(l+r)/2;
if(st<=m) query(2*nod,l,m);
query(2*nod+1,m+1,r);
}
int main()
{
ifstream f("lupu.in");
ofstream g("lupu.out");
f>>n>>x>>l;
for(i=1;i<=n;i++)
{
f>>d>>a;
v[i].c=a;
v[i].t=(x-d)/l;
}
sort(v+1,v+n+1,comp);
step=0;
for(i=1;i<=n;i++)
{
pozitie=i;
val=v[i].c;
update(1,1,n);
}
step=0;val=-1;st=1;
while(st<=n&&step<=n)
{
while(v[st].t<step&&st<=n)
st++;
mx=0;
query(1,1,n);
if(mx!=-1)sum+=mx;
else step=n+1;
update(1,1,n);
step++;
}
g<<sum;
return 0;
}