Submission #1285948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1285948		MMihalev	Soccer Stadium (IOI23_soccer)	C++20	8 / 100	4607 ms	435928 KiB

soccer

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<queue>
#include<set>
#include "soccer.h"
using namespace std;
const int MAX_N=2e3+3;
int n;
int a[MAX_N][MAX_N];
int p[MAX_N][MAX_N];
int lastok[2][MAX_N][MAX_N];//0 : back  |  1 : forward
set<int>block[MAX_N];

bool allempty(int x1,int y1,int x2,int y2)
{
    int x11=min(x1,x2),x22=max(x1,x2);
    int y11=min(y1,y2),y22=max(y1,y2);
    x1=x11+1;y1=y11+1;x2=x22+1;y2=y22+1;
    if(p[x2][y2]-p[x1-1][y2]-p[x2][y1-1]+p[x1-1][y1-1]==(x2-x1+1)*(y2-y1+1))return 1;
    return 0;
}

int tree[2][2][MAX_N][4*MAX_N];
int lazy[2][2][MAX_N][4*MAX_N];
void push_lazy(int topbottom,int dir,int node,int l,int r,int row)
{
    tree[topbottom][dir][row][node]=max(tree[topbottom][dir][row][node],lazy[topbottom][dir][row][node]);
    if(l!=r)
    {
        lazy[topbottom][dir][row][2*node]=max(lazy[topbottom][dir][row][2*node],lazy[topbottom][dir][row][node]);
        lazy[topbottom][dir][row][2*node+1]=max(lazy[topbottom][dir][row][2*node+1],lazy[topbottom][dir][row][node]);
    }
    lazy[topbottom][dir][row][node]=0;
}
void update(int topbottom,int dir,int node,int l,int r,int row,int ql,int qr,int val)
{
    push_lazy(topbottom,dir,node,l,r,row);
    if(r<ql or l>qr)return;
    if(ql<=l && r<=qr)
    {
        lazy[topbottom][dir][row][node]=max(lazy[topbottom][dir][row][node],val);
        push_lazy(topbottom,dir,node,l,r,row);
        return;
    }
    int mid=(l+r)/2;
    update(topbottom,dir,2*node,l,mid,row,ql,qr,val);
    update(topbottom,dir,2*node+1,mid+1,r,row,ql,qr,val);
    tree[topbottom][dir][row][node]=max(tree[topbottom][dir][row][2*node],tree[topbottom][dir][row][2*node+1]);
}
int query(int topbottom,int dir,int node,int l,int r,int row,int idx)
{
    push_lazy(topbottom,dir,node,l,r,row);
    if(r<idx or l>idx)return -1;
    if(l==r)
    {
        return tree[topbottom][dir][row][node];
    }
    int mid=(l+r)/2;
    return max(query(topbottom,dir,2*node,l,mid,row,idx),query(topbottom,dir,2*node+1,mid+1,r,row,idx));
}

void rowupdate(int topbottom,int row,int leftborder,int rightborder,int cur)
{
    auto it=block[row].lower_bound(leftborder);
    int first=(*(it));
    if(first>rightborder+1)return;
    auto it2=block[row].upper_bound(rightborder);
    int last=(*(it2));
    if(last>rightborder+1)
    {
        it2--;
    }
    last=(*(it2));

    if(leftborder<=last-1)update(topbottom,1,1,0,n-1,row,leftborder,last-1,cur);
    if(first+1<=rightborder)update(topbottom,0,1,0,n-1,row,first+1,rightborder,cur);
}

vector<tuple<int,int,bool>>states[MAX_N];
int solve()
{
    int ans=1;

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j])continue;

            int l=j,r=lastok[1][i][j];
            states[r-l+1].push_back({i,j,1});
            l=lastok[0][i][j];r=j;
            states[r-l+1].push_back({i,j,0});
        }
    }
    for(int len=1;len<=n;len++)sort(states[len].rbegin(),states[len].rend());

    for(int len=n;len>=1;len--)
    {
        for(auto [row,col,dir]:states[len])
        {
            int leftborder=min(col,lastok[dir][row][col]),rightborder=max(col,lastok[dir][row][col]);

            int l=row,r=n-1;
            int row2;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(allempty(row,leftborder,mid,rightborder))
                {
                    row2=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }

            int cur=len+query(0,dir,1,0,n-1,row,col);
            ans=max(ans,cur);

            if(row-1>=0)
            {
                l=0;r=row;
                int row3;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(allempty(mid,leftborder,row,rightborder))
                    {
                        row3=mid;
                        r=mid-1;
                    }
                    else l=mid+1;
                }
                if(row3>0)rowupdate(0,row3-1,leftborder,rightborder,cur+(row-row3)*len);
                else
                {
                    ans=max(ans,cur+row*len);
                }
            }
            if(row2+1<n)rowupdate(1,row2+1,leftborder,rightborder,cur);
        }
        ///minimum at the top


        reverse(states[len].begin(),states[len].end());
        for(auto [row,col,dir]:states[len])
        {
            int leftborder=min(col,lastok[dir][row][col]),rightborder=max(col,lastok[dir][row][col]);

            int l=0,r=row;
            int row2;
            while(l<=r)
            {
                int mid=(l+r)/2;
                if(allempty(mid,leftborder,row,rightborder))
                {
                    row2=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }

            int cur=len+query(1,dir,1,0,n-1,row,col);
            ans=max(ans,cur);

            if(row2-1>=0)rowupdate(0,row2-1,leftborder,rightborder,cur);
            if(row+1<n)
            {
                l=row;r=n-1;
                while(l<=r)
                {
                    int mid=(l+r)/2;
                    if(allempty(row,leftborder,mid,rightborder))
                    {
                        row2=mid;
                        l=mid+1;
                    }
                    else r=mid-1;
                }
                if(row2+1<n)rowupdate(1,row2+1,leftborder,rightborder,cur+(row2-row)*len);
                else
                {
                    ans=max(ans,cur+(row2-row)*len);
                }
            }
        }
        ///minimum at the bottom
    }
    return ans;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    for(int i=0;i<n;i++)
    {
        block[i].insert(-1);
        block[i].insert(n);
        for(int j=0;j<n;j++)
        {
            a[i][j]=F[i][j];
            if(a[i][j])block[i].insert(j);
        }
    }

    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            p[i][j]=(a[i-1][j-1]==0)+p[i-1][j]+p[i][j-1]-p[i-1][j-1];
        }
    }

    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j])continue;
            if(j==0 or a[i][j-1])
            {
                lastok[0][i][j]=j;
                continue;
            }
            lastok[0][i][j]=lastok[0][i][j-1];
        }
        for(int j=n-1;j>=0;j--)
        {
            if(a[i][j])continue;
            if(j==n-1 or a[i][j+1])
            {
                lastok[1][i][j]=j;
                continue;
            }
            lastok[1][i][j]=lastok[1][i][j+1];
        }
    }

    return solve();
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 6
• Subtask 2: 8 / 8
• Subtask 3: 0 / 22
• Subtask 4: 0 / 18
• Subtask 5: 0 / 16
• Subtask 6: 0 / 30