제출 #1286115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286115		MMihalev	Soccer Stadium (IOI23_soccer)	C++20	8 / 100	4620 ms	774132 KiB

soccer

#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<queue>
#include<set>
#include<cstring>
#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)
{
    if(y1<0)return 0;
    if(y2>=n)return 0;
    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-1);
    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<pair<int,int>,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({{l,r},i,j,1});
            l=lastok[0][i][j];r=j;
            if(lastok[1][i][l]==r)continue;
            states[r-l+1].push_back({{l,r},i,j,0});
        }
    }
    for(int len=1;len<=n;len++)sort(states[len].rbegin(),states[len].rend());

    for(int len=n;len>=1;len--)
    {
        vector<int>pre;
        for(int id=0;id<states[len].size();id++)
        {
            pair<int,int>borders;
            int row,col,dir;
            tie(borders,row,col,dir)=states[len][id];
            pre.push_back(len+query(0,dir,1,0,n-1,row,col));
        }
        reverse(pre.begin(),pre.end());

        for(int id=0;id<states[len].size();id++)
        {
            int row,col,dir;
            pair<int,int>borders;
            tie(borders,row,col,dir)=states[len][id];
            int leftborder=borders.first,rightborder=borders.second;

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

            int cur=max(len+query(0,dir,1,0,n-1,row,col)+(row-rowtop)*len,
                        len+query(1,dir,1,0,n-1,row,col));
            //cout<<row<<" "<<leftborder<<" "<<rightborder<<" "<<rowtop<<"  "<<len+query(0,dir,1,0,n-1,row,col)+(row-rowtop)*len<<" "<<len+query(1,dir,1,0,n-1,row,col)<<"\n";
            ans=max(ans,cur);
            if(rowtop-1>=0)
            {
                rowupdate(0,rowtop-1,leftborder,rightborder,cur);
            }
        }
        ///minimum at the top


        reverse(states[len].begin(),states[len].end());
        for(int id=0;id<states[len].size();id++)
        {
            int row,col,dir;
            pair<int,int>borders;
            tie(borders,row,col,dir)=states[len][id];
            int leftborder=borders.first,rightborder=borders.second;

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

            int cur=max(len+query(1,dir,1,0,n-1,row,col)+(rowbottom-row)*len,
                        pre[id]);
            //cout<<row<<" "<<leftborder<<" "<<rightborder<<" "<<rowbottom<<"  "<<pre[id]<<" "<<len+query(1,dir,1,0,n-1,row,col)+(rowbottom-row)*len<<"\n";
            ans=max(ans,cur);
            if(rowbottom+1<n)
            {
                rowupdate(1,rowbottom+1,leftborder,rightborder,cur);
            }
        }
        ///minimum at the bottom
    }
    return ans;
}


vector<pair<int,int>>intervals;
int b[MAX_N][MAX_N];
bool inside(int i,int j)
{
    if(intervals[j].first<=intervals[i].first && intervals[j].second>=intervals[i].second)return 1;
    return 0;
}
bool check()
{
    intervals.clear();
    int hasprev=0,haslast=0;
    for(int i=0;i<n;i++)
    {
        int f=-1,s=-2;
        for(int j=0;j<n;j++)
        {
            if(b[i][j]==0)
            {
                if(f==-1)f=j;
                s=j;
            }
        }
        for(int j=f;j<=s;j++)
        {
            if(b[i][j])return 0;
        }
        int hasnow=(f!=-1 ? 1 : 0);
        if(hasnow)
        {
            intervals.push_back({f,s});
            if(haslast==0 && hasprev)return 0;
        }
        haslast=hasnow;
        hasprev=max(hasprev,hasnow);
    }

    for(int i=1;i<intervals.size();i++)
    {
        if(inside(i-1,i))continue;

        for(int j=i;j<intervals.size();j++)
        {
            if(inside(j,j-1))
            {
                continue;
            }
            return 0;
        }

        break;
    }
    for(int i=0;i<intervals.size();i++)intervals[i].second*=-1;

    sort(intervals.begin(),intervals.end());
     for(int i=0;i<intervals.size();i++)intervals[i].second*=-1;
    for(int i=1;i<intervals.size();i++)
    {
        if(inside(i,i-1))continue;
        return 0;
    }

    return 1;
}

int shit()
{
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            b[i][j]=1;
        }
    }

    vector<pair<int,int>>cells;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            if(a[i][j]==0)cells.push_back({i,j});
        }
    }
    int sz=cells.size();
    vector<pair<int,int>>masks;
    for(int mask=1;mask<(1<<sz);mask++)
    {
        masks.push_back({__builtin_popcount(mask),mask});
    }
    sort(masks.rbegin(),masks.rend());
    for(auto [cnt,mask]:masks)
    {
        for(int i=0;i<sz;i++)
        {
            if(((1<<i)&(mask))==0)continue;
            int x=cells[i].first,y=cells[i].second;
            b[x][y]=0;
        }
        bool ok=check();
        for(int i=0;i<sz;i++)
        {
            if(((1<<i)&(mask))==0)continue;
            int x=cells[i].first,y=cells[i].second;
            b[x][y]=1;
        }
        if(ok)return cnt;
    }
    return 1;
}

void reset()
{
    memset(tree,0,sizeof(tree));
    memset(lazy,0,sizeof(lazy));
    memset(a,0,sizeof(a));
    memset(b,0,sizeof(b));
    memset(p,0,sizeof(p));
    memset(lastok,0,sizeof(lastok));
    for(int i=0;i<n;i++)
    {
        block[i].clear();
    }
    for(int i=1;i<=n;i++)
    {
        states[i].clear();
    }
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
    n=N;
    reset();
    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];
        }
    }
    /*int x=solve(),y=shit();
    if(x!=y)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                cout<<a[i][j]<<" ";
            }
            cout<<"\n";
        }
        cout<<"\n";
        cout<<"Correct : "<<y<<"\n";
        cout<<"My idea : "<<x<<"\n";
        return 1;
    }
    return 0;*/

    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