Problema 1: Grilla

La solución inicial de 60 puntos utiliza un enfoque ineficiente O(n⁴). La versión óptima mantiene componentes conectados mediante una estructura union-find. Al desplazar una ventana de m×m, solo se actualizan las dos columnas afectadas. Se calcula el área máxima sumando el tamaño de los componentes adyacentes a la ventana.

#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
const int L=505;
int gridSize,windowSize,maxConnected,tempSum,total,grid[L][L],parent[L*L],compSize[L*L];
int dx[4]={0,0,1,-1},dy[4]={1,-1,0,0};
vector<int> buffer;

int getIndex(int x,int y){return (x-1)*gridSize+y;}
int findRoot(int x){
    if(parent[x]!=x) parent[x]=findRoot(parent[x]);
    return parent[x];
}

void initWindow(int row,int col){
    tempSum=0; buffer.clear();
    for(int i=row;i<row+windowSize;i++)
        for(int j=col;j<col+windowSize;j++)
            if(grid[i][j]) compSize[findRoot(getIndex(i,j))]--;
    
    for(int i=1;i<=windowSize;i++){
        if(row>1&&grid[row-1][i]) buffer.push_back(findRoot(getIndex(row-1,i)));
        if(row+windowSize<=gridSize&&grid[row+windowSize][i]) buffer.push_back(findRoot(getIndex(row+windowSize,i)));
        if(grid[row+i-1][windowSize+1]) buffer.push_back(findRoot(getIndex(row+i-1,windowSize+1)));
    }
    sort(buffer.begin(),buffer.end());
    buffer.erase(unique(buffer.begin(),buffer.end()),buffer.end());
    for(auto& idx:buffer) tempSum+=compSize[idx];
    maxConnected=max(maxConnected,windowSize*windowSize+tempSum);
}

void slideWindow(int row,int col){
    for(int i=1;i<=windowSize;i++){
        if(grid[row+i-1][col-1]) compSize[findRoot(getIndex(row+i-1,col-1))]++;
        if(grid[row+i-1][col+windowSize-1]) compSize[findRoot(getIndex(row+i-1,col+windowSize-1))]--;
    }
    buffer.clear(); tempSum=0;
    for(int i=1;i<=windowSize;i++){
        if(row>1&&grid[row-1][col+i-1]) buffer.push_back(findRoot(getIndex(row-1,col+i-1)));
        if(col>1&&grid[row+i-1][col-1]) buffer.push_back(findRoot(getIndex(row+i-1,col-1)));
        if(row+windowSize<=gridSize&&grid[row+windowSize][col+i-1]) buffer.push_back(findRoot(getIndex(row+windowSize,col+i-1)));
        if(col+windowSize<=gridSize&&grid[row+i-1][col+windowSize]) buffer.push_back(findRoot(getIndex(row+i-1,col+windowSize)));
    }
    sort(buffer.begin(),buffer.end());
    buffer.erase(unique(buffer.begin(),buffer.end()),buffer.end());
    for(auto& idx:buffer) tempSum+=compSize[idx];
    maxConnected=max(maxConnected,windowSize*windowSize+tempSum);
}

void restoreWindow(int row,int col){
    for(int i=row;i<row+windowSize;i++)
        for(int j=col;j<col+windowSize;j++)
            if(grid[i][j]) compSize[findRoot(getIndex(i,j))]++;
}

int main(){
    ios::sync_with_stdio(0);
    cin>>gridSize>>windowSize;
    if(windowSize>=gridSize){cout<<gridSize*gridSize;return 0;}
    for(int i=1;i<=gridSize;i++){
        string s; cin>>s;
        for(int j=1;j<=gridSize;j++){
            compSize[++total]=grid[i][j]=(s[j-1]=='.');
            parent[total]=total;
        }
    }
    for(int i=1;i<=gridSize;i++)
        for(int j=1;j<=gridSize;j++)
            if(grid[i][j])
                for(int k=0;k<4;k++){
                    int nx=i+dx[k],ny=j+dy[k];
                    if(nx<1||nx>gridSize||ny<1||ny>gridSize||!grid[nx][ny]) continue;
                    int u=findRoot(getIndex(i,j)),v=findRoot(getIndex(nx,ny));
                    if(u==v) continue;
                    compSize[v]+=compSize[u];
                    parent[u]=v;
                }
    for(int i=1;i<=gridSize-windowSize+1;i++){
        initWindow(i,1);
        for(int j=2;j<=gridSize-windowSize+1;j++) slideWindow(i,j);
        restoreWindow(i,gridSize-windowSize+1);
    }
    cout<<maxConnected;
}

Problema 2: Secuencia

Se resuelve con programación dinámica optimizada mediante CDQ. La transición de j a i requiere que i>j, s[i]>s[j] y s[i]-i≤s[j]-j. Se utiliza un árbol de Fenwick para manejar la tercera condición después de comprimir coordenadas.

#include<iostream>
#include<algorithm>
#include<vector>
#define ll long long
using namespace std;
const int N=5e5+10;
int n,ans,cnt,dp[N],temp[N];
struct Element{int id,val,comp;};
Element arr[N];

struct FenwickTree{
    int tree[N];
    int lowbit(int x){return x&-x;}
    void reset(int pos){for(int i=pos;i;i-=lowbit(i))tree[i]=0;}
    void update(int pos,int val){for(int i=pos;i;i-=lowbit(i))tree[i]=max(tree[i],val);}
    int query(int pos){int res=0;for(int i=pos;i<=cnt;i+=lowbit(i))res=max(res,tree[i]);return res;}
}BIT;

void CDQ(int l,int r){
    if(l==r){dp[l]=max(dp[l],(arr[l].val<=n)*1LL);return;}
    int mid=(l+r)>>1;
    CDQ(l,mid);
    sort(arr+l,arr+mid+1,[](Element a,Element b){
        return a.val==b.val?a.comp<b.comp:a.val<b.val;
    });
    sort(arr+mid+1,arr+r+1,[](Element a,Element b){
        return a.val==b.val?a.comp<b.comp:a.val<b.val;
    });
    int i=l;
    for(int j=mid+1;j<=r;j++){
        while(i<=mid&&arr[i].val<=arr[j].val){
            if(arr[i].val<=arr[i].id) BIT.update(arr[i].comp,dp[arr[i].id]);
            i++;
        }
        if(arr[j].val>arr[l].val&&i>l) 
            dp[arr[j].id]=max(dp[arr[j].id],BIT.query(arr[j].comp)+1);
    }
    for(int k=l;k<i;k++) 
        if(arr[k].val<=arr[k].id) BIT.reset(arr[k].comp);
    sort(arr+mid+1,arr+r+1,[](Element a,Element b){return a.id<b.id;});
    CDQ(mid+1,r);
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>arr[i].val;
        arr[i].id=i;
        temp[i]=arr[i].val-i;
    }
    sort(temp+1,temp+n+1);
    cnt=unique(temp+1,temp+n+1)-temp-1;
    for(int i=1;i<=n;i++) 
        arr[i].comp=lower_bound(temp+1,temp+cnt+1,arr[i].val-i)-temp;
    CDQ(1,n);
    for(int i=1;i<=n;i++) ans=max(ans,dp[i]);
    cout<<ans;
}