Help! WA11
Posted by
zwqzwq 2 Aug 2021 16:57
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;
struct dw
{
ll a,f,s;
}A[1600];
bool cmp(dw n1,dw n2)
{
if(n1.a==n2.a)
{
if(n1.f==n2.f)return n1.s<n2.s;
else return n1.f<n2.f;
}
else return n1.a<n2.a;
}
ll ys1[1600],ys2[1600];
ll ans,ad,au,al,ar;
struct node
{
ll l,r,lc,rc,lmax,ln,rmax,rn,mmax,sum,nn;
ll L,R,lR,rL;
bool have;
}tr[3100];ll trlen=0;
ll da=1501;
void update(ll now)
{
ll lc=tr[now].lc,rc=tr[now].rc;
tr[now].sum=tr[lc].sum+tr[rc].sum;
tr[now].nn=tr[lc].nn+tr[rc].nn;
ll qwq=-da,ql,qr;
if(tr[lc].have){if(tr[lc].mmax>qwq){qwq=tr[lc].mmax;ql=tr[lc].L,qr=tr[lc].R;}}
if(tr[rc].have){if(tr[rc].mmax>qwq){qwq=tr[rc].mmax;ql=tr[rc].L,qr=tr[rc].R;}}
if(tr[lc].rn+tr[rc].ln>=2){if(tr[lc].rmax+tr[rc].lmax>qwq){qwq=tr[lc].rmax+tr[rc].lmax;ql=tr[lc].rL;qr=tr[rc].lR;}}
if(qwq==-da)tr[now].have=false,tr[now].mmax=tr[now].L=tr[now].R=0;
else tr[now].have=true,tr[now].mmax=qwq,tr[now].L=ql,tr[now].R=qr;
tr[now].lmax=tr[lc].lmax,tr[now].ln=tr[lc].ln,tr[now].lR=tr[lc].lR;
if(tr[lc].sum+tr[rc].lmax>=tr[now].lmax)tr[now].lmax=tr[lc].sum+tr[rc].lmax,tr[now].ln=tr[lc].nn+tr[rc].ln,tr[now].lR=tr[rc].lR;
tr[now].rmax=tr[rc].rmax,tr[now].rn=tr[rc].rn,tr[now].rL=tr[rc].rL;
if(tr[rc].sum+tr[lc].rmax>=tr[now].rmax)tr[now].rmax=tr[rc].sum+tr[lc].rmax,tr[now].rn=tr[rc].nn+tr[lc].rn,tr[now].rL=tr[lc].rL;
}
void bt(ll l,ll r)
{
ll now=++trlen;tr[now].l=l;tr[now].r=r;tr[now].lc=tr[now].rc=-1;
tr[now].mmax=0;tr[now].have=0;tr[now].lmax=tr[now].rmax=0;tr[now].ln=tr[now].rn=0;tr[now].sum=tr[now].nn=0;
tr[now].L=tr[now].R=tr[now].lR=tr[now].rL=0;
if(l<r)
{
ll mid=(l+r)/2;
tr[now].lc=trlen+1;bt(l,mid);
tr[now].rc=trlen+1;bt(mid+1,r);
update(now);
}
else tr[now].lR=tr[now].rL=l;
}
void change(ll now,ll x,ll k)
{
if(tr[now].l==tr[now].r)
{
tr[now].sum+=k;tr[now].nn++;
tr[now].lmax=tr[now].rmax=tr[now].sum;
tr[now].ln=tr[now].rn=tr[now].nn;
if(tr[now].nn>=2)tr[now].mmax=tr[now].sum,tr[now].L=tr[now].R=x,tr[now].have=true;
}
else
{
ll lc=tr[now].lc,rc=tr[now].rc,mid=(tr[now].l+tr[now].r)/2;
if(x<=mid)change(lc,x,k);
else change(rc,x,k);
update(now);
}
}
ll n,z1,z2;
void solve()
{
for(ll i=1;i<=n;i++)
{
trlen=0;bt(1,z2);
ll st1=A[i].a,st=i;
for(ll j=st1;j<=z1;j++)
{
bool bk=false;
while(st<=n&&A[st].a==j){change(1,A[st].f,A[st].s);st++;bk=1;}
if(bk)
{
if(tr[1].have)
{
if(ans<tr[1].mmax)
{
ans=tr[1].mmax;
au=st1;ad=j;
al=tr[1].L,ar=tr[1].R;
}
}
}
}
while(i<n&&A[i+1].a==st1)i++;
}
}
struct ls
{
ll x,id;
}AA[1600];
bool cmp1(ls n1,ls n2){return n1.x<n2.x;}
int main()
{
da*=1000000000;
scanf("%lld",&n);ll z;
for(ll i=1;i<=n;i++)scanf("%lld%lld%lld",&A[i].a,&A[i].f,&A[i].s);
for(ll i=1;i<=n;i++)AA[i].x=A[i].a,AA[i].id=i;
sort(AA+1,AA+n+1,cmp1);z=0;
for(ll i=1;i<=n;i++)
{
if(i==1||AA[i].x!=AA[i-1].x){z++;ys1[z]=AA[i].x;}
A[AA[i].id].a=z;
}z1=z;
for(ll i=1;i<=n;i++)AA[i].x=A[i].f,AA[i].id=i;
sort(AA+1,AA+n+1,cmp1);z=0;
for(ll i=1;i<=n;i++)
{
if(i==1||AA[i].x!=AA[i-1].x){z++;ys2[z]=AA[i].x;}
A[AA[i].id].f=z;
}z2=z;
sort(A+1,A+n+1,cmp);
ans=-da;solve();
printf("%lld %lld\n%lld %lld\n",ys1[au],ys1[ad],ys2[al],ys2[ar]);
return 0;
}