Submission #1145678

#	Time	Username	Problem	Language	Result	Execution time	Memory
1145678		Math4Life2020	Soccer Stadium (IOI23_soccer)	C++20	8 / 100	281 ms	192080 KiB

soccer

#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;

const ll Nm = 2048; const ll E = 11; const ll INF = 1e7;
ll N;
ll ans = 0;
ll stt[Nm][2*Nm]; //y, x-segtree (coordinate of closest top point)
ll stb[Nm][2*Nm]; //same but bottom
ll nxtr[Nm][Nm];
map<ll,ll> m0[Nm+1]; //m0[top-bottom][COORDINATE COMPRESSION]->value
//COORD COMPR: (left)<<33+(right)<<22+(top)<<11+bottom

inline ll v2(ll x) {
    return __builtin_ctz(x);
}

ll gtb(ll xl, ll xr, ll y0) {
    if (xl>xr) {
        return -1;
    }
    ll vl = v2(xl); ll vr = v2(xr+1);
    if (vl<vr) {
        return max(stb[y0][(xl>>vl)+(1<<(E-vl))],gtb(xl+(1<<vl),xr,y0));
    } else {
        return max(stb[y0][(xr>>vr)+(1<<(E-vr))],gtb(xl,xr-(1<<vr),y0));
    }
}

ll gtt(ll xl, ll xr, ll y0) {
    if (xl>xr) {
        return N;
    }
    ll vl = v2(xl); ll vr = v2(xr+1);
    if (vl<vr) {
        return min(stt[y0][(xl>>vl)+(1<<(E-vl))],gtt(xl+(1<<vl),xr,y0));
    } else {
        return min(stt[y0][(xr>>vr)+(1<<(E-vr))],gtt(xl,xr-(1<<vr),y0));
    }
}

pii gt(ll xl, ll xr, ll y0) {
    pii gtp ={gtb(xl,xr,y0),gtt(xl,xr,y0)};
    //cerr << "xl="<<xl<<",xr="<<xr<<",y0="<<y0<<"; gtp="<<gtp.first<<","<<gtp.second<<"\n";
    assert(gtp.second>=gtp.first);
    //exit(0);
    return gtp;
}

ll biggest_stadium(int _N, vector<vector<int>> F) {
    N = _N;
    //cout << "N="<<N<<"\n";
    for (ll i=0;i<N;i++) { //view as coordinates (j,i), screw original system
        for (ll j=0;j<N;j++) {
            if (F[i][j]==1) {
                stt[i][j+Nm]=i;
                stb[i][j+Nm]=i;
            } else {
                stt[i][j+Nm]=N;
                stb[i][j+Nm]=-1;
            }
            if (i>=1) {
                stb[i][j+Nm]=max(stb[i][j+Nm],stb[i-1][j+Nm]);
            }
        }
        ll nval = N;
        for (ll j=(N-1);j>=0;j--) {
            if (F[i][j]==1) {
                nval = j;
            }
            nxtr[i][j]=nval;
        }
    }
    for (ll i=(N-2);i>=0;i--) {
        for (ll j=0;j<N;j++) {
            stt[i][j+Nm]=min(stt[i][j+Nm],stt[i+1][j+Nm]);
        }
    }
    for (ll i=0;i<N;i++) {
        for (ll j=(Nm-1);j>=1;j--) {
            stt[i][j]=min(stt[i][2*j],stt[i][2*j+1]);
            stb[i][j]=max(stb[i][2*j],stb[i][2*j+1]);
        }
    }
    for (ll i=0;i<N;i++) {
        ll rj = N-1;
        for (ll j=(N-1);j>=-1;j--) {
            if (j==-1 || F[i][j]==1) {
                if (rj>j) {
                    pii ph = gt(j+1,rj,i);
                    ph.first++; ph.second--;
                    if (ph.second>=ph.first) {
                        //cout << "new box1: "<<(j+1)<<","<<(rj)<<","<<(ph.second)<<","<<ph.first<<"\n";
                        m0[ph.second-ph.first][((j+1)<<33)+(rj<<22)+(ph.second<<11)+(ph.first)]=(ph.second-ph.first+1)*(rj-j);
                    }
                    rj = j;
                }
            }
        }
    }
    //exit(0);
    for (ll H0=0;H0<=N;H0++) {
        for (pii PT: m0[H0]) {
            ll MSK = PT.first; ll VAL = PT.second;
            ans = max(ans,VAL);
            ll xl = (MSK>>33)&(2047);
            ll xr = (MSK>>22)&(2047);
            ll yr = (MSK>>11)&(2047);
            ll yl = (MSK)&(2047);
            //cout << "process xl,xr,yl,yr="<<xl<<","<<xr<<","<<yl<<","<<yr<<"\n";
            if (yr<(N-1)) {
                ll xc = xl;
                ll xn = xl;
                while (xc <= xr) {
                    xn = nxtr[yr+1][xc];
                    if (xn>xr) {
                        xn = xr+1;
                    }
                    if (xc<xn) {
                        pii ph = gt(xc,xn-1,yr+1);
                        ph.second--; ph.first++;
                        if ((ph.second-ph.first)>H0) {
                            //cout << "new box2: "<<(xc)<<","<<(xn-1)<<","<<(ph.second)<<","<<(ph.first)<<"\n";
                            if (m0[ph.second-ph.first].find(((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first))==m0[ph.second-ph.first].end()) {
                                m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)]=0;
                            }
                            m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)]=max(m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)],VAL+(ph.second-ph.first+1)*(xn-xc)-(yr-yl+1)*(xn-xc));
                        }
                    }
                    xc = xn+1;
                }
            }
            if (yl>0) {
                ll xc = xl;
                ll xn = xl;
                while (xc <= xr) {
                    xn = nxtr[yl-1][xc];
                    if (xn>xr) {
                        xn = xr+1;
                    }
                    if (xc<xn) {
                        pii ph = gt(xc,xn-1,yl-1);
                        ph.second--; ph.first++;
                        if ((ph.second-ph.first)>H0) {
                            //cout << "new box3: "<<(xc)<<","<<(xn-1)<<","<<(ph.second)<<","<<(ph.first)<<"\n";
                            if (m0[ph.second-ph.first].find(((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first))==m0[ph.second-ph.first].end()) {
                                m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)]=0;
                            }
                            m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)]=max(m0[ph.second-ph.first][((xc)<<33)+((xn-1)<<22)+(ph.second<<11)+(ph.first)],VAL+(ph.second-ph.first+1)*(xn-xc)-(yr-yl+1)*(xn-xc));
                        }
                    }
                    xc = xn+1;
                }
            }
        }
    }
    return ans;
}

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