#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;
}

I use segment tree to solve this problems(O(n^2logn)).
And I have checked my program with an solution(already accepted) for many times.
All my answer is correct.
But still wa#2.
Sorry for my poor English.
Please help me,Thank you.

I think can set a challege problem  with range n<=1e5...

Try this:
2
1 1 1
1 1 1
Answer:
1 1
1 1
Good luck!

Hi guys,

   I am trying to solve this problem. But I am not able to understand the the Input and Output which was given.

   Can anyone help me in understanding the problem, I possible please send me the code.
   Email: korapatimanoj@gmail.com
   Thanks in advance...

Regards,
Manu

does 2 5 contains 5?

After sorting we have the problem of
finding maximal-sum submatrix
but it has O(n^3).
After additional thinking- all OK!
This is the way.For eaach row range [i1,i2]
it should  mantain set of nonzero columns
and number of such colums in mean must be 1-10

Pardon...Tle. Instead 1-10 really we have 500

Edited by author 19.10.2009 20:45