bu ne lan matematik c algoritma kasiyonuz

alin ipneler

8. include <iostream>
9. include <cstdio>
10. include <algorithm>
11. include <limits>
12. define MAXAR 2000100
13. define ll long long
14. define INF 40000000000LL
using namespace std;

FILE *in,*out;
struct node{
int t,d,c;
}ar[500100];
int N,IN,CIK,ST,MAXD=0;
bool operator < (node p,node q)
{
if(p.t!=q.t) return p.t>q.t;
return p.d>q.d;
}

class KDtree{
ll DEG,*ar;
int ILK,SON,NER;
ll ver(int root,int ilk,int son)
{
if(ILK<=ilk && son<=SON) return ar[root];
if(ILK>=son || SON<=ilk) return -INF;
return max(ver(root*2+1,ilk,(ilk+son)/2),ver(root*2+2,(ilk+son)/2,son));
}
ll ekle(int root,int ilk,int son)
{
if(NER<ilk || NER>=son) return ar[root];
if(NER

ilk && ilk

son-1){ar[root]=DEG;return ar[root];}
ar[root]=max(ekle(root*2+1,ilk,(ilk+son)/2),ekle(root*2+2,(ilk+son)/2,son));
return ar[root];
}
public:ll start(ll *AR)
{
int t,z,v;
for(t=0;t<=MAXAR;t++)
AR[t]=-INF;
return 1;
}
public:ll giveMAX(ll *AR,int ilk,int son)
{
ar=AR;
ILK=ilk;
SON=son;
return ver(0,0,MAXD+1);
}
public:ll add(ll *AR,int ner,ll deg)
{
ar=AR;
NER=ner;
DEG=deg;
return ekle(0,0,MAXD+1);
}
};

KDtree compile;
ll ar_sol[MAXAR+2];
ll ar_sag[MAXAR+2];
ll ar_solx[MAXAR+2];
ll ar_sagx[MAXAR+2];
ll ar_soly[MAXAR+2];
ll ar_sagy[MAXAR+2];

int read()
{
int t,z,v;
fscanf(in,"%d %d %d %d",&N,&IN,&CIK,&ST);
for(t=0;t<N;t++)
{
fscanf(in,"%d %d %d",&ar[t].t,&ar[t].d,&ar[t].c);
MAXD=max(MAXD,ar[t].d);
}
MAXD++;
sort(ar,ar+N);
}

inline ll hes(int ilk,int son)
{
if(ilk<son) return ((ll)son-ilk)*CIK;
return ((ll)ilk-son)*IN;
}

int pre()
{
compile. start(ar_sol);
compile. start(ar_sag);
compile. start(ar_solx);
compile. start(ar_sagx);
compile. start(ar_soly);
compile. start(ar_sagy);
}

int make_60()
{
int t,z,v,ilk,son;
ll gmax;
for(t=0;t<N;t++)
{
gmax=-hes(ar[t].d,ST);
gmax=max(gmax, compile.giveMAX(ar_sol,ar[t].d+1,MAXD)+hes(0,ar[t].d));
gmax=max(gmax, compile.giveMAX(ar_sag,0,ar[t].d)+hes(MAXD,ar[t].d));
// printf("%lldn",gmax+ar[t].c);
compile.add(ar_sol,ar[t].d,(gmax+ar[t].c)-hes(0,ar[t].d));
compile.add(ar_sag,ar[t].d,(gmax+ar[t].c)-hes(MAXD,ar[t].d));
}
gmax=0;
gmax=max(gmax, compile.giveMAX(ar_sol,ST+1,MAXD)+hes(0,ST));
gmax=max(gmax, compile.giveMAX(ar_sag,0,ST)+hes(MAXD,ST));
fprintf(out,"%dn",gmax);
}

int olustur_solx(int ilk,int son)
{
int t,z,v;
ll gmax;
for(t=ilk;t<son;t++)
{
gmax=-hes(ar[t].d,ST);
gmax=max(gmax, compile.giveMAX(ar_sol,0,ar[t].d)+hes(MAXD,ar[t].d));
gmax=max(gmax, compile.giveMAX(ar_sag,ar[t].d+1,MAXD)+hes(0,ar[t].d));
gmax=max(gmax, compile.giveMAX(ar_solx,0,ar[t].d)+hes(MAXD,ar[t].d));
compile.add(ar_solx,ar[t].d,(gmax+ar[t].c)-hes(MAXD,ar[t].d));
}
}

int olustur_sagx(int ilk,int son)
{
int t,z,v;
ll gmax;
for(t=son-1;t>=ilk;t--)
{
gmax=-hes(ar[t].d,ST);
gmax=max(gmax, compile.giveMAX(ar_sol,0,ar[t].d)+hes(MAXD,ar[t].d));
gmax=max(gmax, compile.giveMAX(ar_sag,ar[t].d+1,MAXD)+hes(0,ar[t].d));
gmax=max(gmax, compile.giveMAX(ar_sagx,ar[t].d+1,MAXD)+hes(0,ar[t].d));
compile.add(ar_sagx,ar[t].d,(gmax+ar[t].c)-hes(0,ar[t].d));
}
}

int olustur_soly(int ilk,int son)
{
int t,z,v;
ll gmax;
for(t=ilk;t<son;t++)
{
gmax=0;
gmax=max(gmax, compile.giveMAX(ar_soly,0,ar[t].d)+hes(MAXD,ar[t].d)+hes(ar[t].d,MAXD));
compile.add(ar_soly,ar[t].d,(gmax+ar[t].c)-hes(MAXD,ar[t].d)-hes(ar[t].d,MAXD));
}
}

int olustur_sagy(int ilk,int son)
{
int t,z,v;
ll gmax;
for(t=son-1;t>=ilk;t--)
{
gmax=0;
gmax=max(gmax, compile.giveMAX(ar_sagy,ar[t].d+1,MAXD)+hes(0,ar[t].d)+hes(ar[t].d,0));
compile.add(ar_sagy,ar[t].d,(gmax+ar[t].c)-hes(0,ar[t].d)-hes(ar[t].d,0));
}
}

int cikar_tumu(int ilk,int son)
{
int t,z,v;
for(t=ilk;t<son;t++)
{
compile.add(ar_solx,ar[t].d,-INF);
compile.add(ar_sagx,ar[t].d,-INF);
compile.add(ar_soly,ar[t].d,-INF);
compile.add(ar_sagy,ar[t].d,-INF);
}
return 0;
}

int make_100()
{
int t,z,v,ilk,son;
ll gmax, gsol,gsag;
for(t=0;t<N;)
{
for(z=t;z<N;z++)
if(ar[z].t!=ar[t].t)
break;
ilk=t;son=z;
// for(z=ilk;z<son;z++)
// printf("<%d,%d,%d> ",ar[z].t,ar[z].d,ar[z].c);
// printf("arasin");
// getchar();
olustur_solx(ilk,son);
olustur_sagx(ilk,son);
// printf("%lldn",compile. giveMAX(ar_solx,1,MAXD));
olustur_soly(ilk,son);
olustur_sagy(ilk,son);
for(z=ilk;z<son;z++)
{
gmax=-hes(ar[z].d,ST);
gsol=compile. giveMAX(ar_solx,0,ar[z].d+1)+hes(MAXD,ar[z].d);
gsag=compile. giveMAX(ar_sagy,ar[z].d,MAXD)+hes(0,ar[z].d)+hes(ar[z].d,0);
gmax=max(gmax, gsol+gsag-ar[z].c);
gsol=compile. giveMAX(ar_soly,0,ar[z].d+1)+hes(MAXD,ar[z].d)+hes(ar[z].d,MAXD);
gsag=compile. giveMAX(ar_sagx,ar[z].d,MAXD)+hes(0,ar[z].d);
gmax=max(gmax, gsol+gsag-ar[z].c);
// printf("%lldn",gmax);
compile.add(ar_sol,ar[z].d,gmax-hes(MAXD,ar[z].d));
compile.add(ar_sag,ar[z].d,gmax-hes(0,ar[z].d));
}
cikar_tumu(ilk,son);
t=son;
}
gmax=0;
gmax=max(gmax, compile.giveMAX(ar_sol,0,ST)+hes(MAXD,ST));
gmax=max(gmax, compile.giveMAX(ar_sag,ST+1,MAXD)+hes(0,ST));
fprintf(out,"%dn",gmax);
}

main()
{
in = fopen("salesman.in","r");
out= fopen("salesman.out","w");
read();
pre();
make_60();
// make_100();
return 0;
}

oz hakiki kendi kodum 6 tane kd tree (interval da deniyo) kastim algoritmainin dibine vurdum ioi 2009 sorusu