Pasari - 80p

#include <fstream>
using namespace std;

ifstream cin("pasari.in");
ofstream cout("pasari.out");

#define MAX_LAT 1000
int v[MAX_LAT][MAX_LAT],frv[MAX_LAT][MAX_LAT];
int st[MAX_LAT][MAX_LAT],dr[MAX_LAT][MAX_LAT];
int sus[MAX_LAT][MAX_LAT],jos[MAX_LAT][MAX_LAT];
int grid[MAX_LAT],smen[MAX_LAT];

void cons(int lin,int n){
    int poz,col;
    st[lin][0]=1;
    poz=1;
    grid[0]=0;
    for(col=1;col< n;col++){
        if(v[lin][grid[poz-1]]>v[lin][col]){
            st[lin][col]=col-grid[poz-1];
            grid[poz]=col+1;
            poz++;
        }else{
            while(poz>0 && v[lin][grid[poz-1]]<=v[lin][col]){
                poz--;
            }
            if(poz==0)
                st[lin][col]=col;
            else
                st[lin][col]=col-grid[poz-1];
            grid[poz]=col;
            poz++;
        }
    }
}
void cond(int lin,int n){
    int poz,col;
    dr[lin][n-1]=1;
    poz=1;
    grid[0]=n-1;
    for(col=n-2;col>=0;col--){
        if(v[lin][grid[poz-1]]>v[lin][col]){
            dr[lin][col]=grid[poz-1]-col;
            grid[poz]=col;
            poz++;
        }else{
            while(poz>0 && v[lin][grid[poz-1]]<=v[lin][col]){
                poz--;
            }
            if(poz==0)
                dr[lin][col]=n-col;
            else
                dr[lin][col]=grid[poz-1]-col;
            grid[poz]=col;
            poz++;
        }
    }
}
void conjos(int col,int n){
    int poz,lin;
    jos[n-1][col]=1;
    poz=1;
    grid[0]=n-1;
    for(lin=n-2;lin>=0;lin--){
        if(v[grid[poz-1]][col]>v[lin][col]){
            jos[lin][col]=grid[poz-1]-lin;
            grid[poz]=lin;
            poz++;
        }else{
            while(poz>0 && v[grid[poz-1]][col]<=v[lin][col]){
                poz--;
            }
            if(poz==0)
                jos[lin][col]=n-lin;
            else
                jos[lin][col]=grid[poz-1]-lin;
            grid[poz]=lin;
            poz++;
        }
    }
}
void consus(int col,int n){
    int poz,lin;
    sus[0][col]=1;
    poz=1;
    grid[0]=0;
    for(lin=1;lin<n;lin++){
        if(v[grid[poz-1]][col]>v[lin][col]){
            sus[lin][col]=lin-grid[poz-1];
            grid[poz]=lin;
            poz++;
        }else{
            while(poz>0 && v[grid[poz-1]][col]<=v[lin][col]){
                poz--;
            }
            if(poz==0)
                sus[lin][col]=lin+1;
            else
                sus[lin][col]=lin-grid[poz-1];
            grid[poz]=lin;
            poz++;
        }
    }
}
int main()
{
    int cer,n,i,lin,col,max1,ccol,s,l;
    cin>>cer>>n;
    if(cer==1)
        cin>>l;
    for(lin=0;lin<n;lin++)
        for(col=0;col<n;col++)
            cin>>v[lin][col];
    for(i=0;i<n;i++){
            consus(i,n);
            conjos(i,n);
            cons(i,n);
            cond(i,n);
    }
    /*-----debug------
    for(lin=0;lin<n;lin++){
        for(col=0;col<n;col++){
            printf("%d %d: sus %d jos %d dreapta %d stanga %d" ,lin,col,sus[lin][col],jos[lin][col],dr[lin][col],st[lin][col]);
            printf("\n");
        }
    }
    ///-----debug------*/
    if(cer==1){
        lin=l-1;
        max1=ccol=0;
        for(col=0;col<n;col++){
            s=dr[lin][col]+st[lin][col]+jos[lin][col]+sus[lin][col]-3;
            if(s>max1){
                max1=s;
                ccol=col+1;
            }
        }
        cout<<ccol;
    }else{
        max1=0;
        for(lin=0;lin<n;lin++){
            for(col=0;col<n;col++){
                smen[col-st[lin][col]+1]+=1;
                smen[col+dr[lin][col]]-=1;
            }
            for(col=1;col<n;col++){
                smen[col]+=smen[col-1];
            }
            for(col=0;col<n;col++){
                frv[lin][col]+=smen[col];
                if(frv[lin][col]>max1)
                    max1=frv[lin][col];
                smen[col]=0;
            }
        }
        for(col=0;col<n;col++){
            for(lin=0;lin<n;lin++){
                smen[lin-sus[lin][col]+1]+=1;
                smen[lin+jos[lin][col]]-=1;
            }
            for(lin=1;lin<n;lin++){
                smen[lin]+=smen[lin-1];
            }
            for(lin=0;lin<n;lin++){
                frv[lin][col]+=smen[lin];
                if(frv[lin][col]>max1)
                    max1=frv[lin][col];
                smen[lin]=0;
            }
        }
        col=lin=0;
        while(frv[lin][col]!=max1){
            col++;
            if(col==n){
                col=0;
                lin++;
            }
        }
        cout<<lin+1<<" "<<col+1;
    }
    return 0;
}