Submission #1110424

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110424		jerzyk	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	2647 ms	798068 KiB

soccer

#include <bits/stdc++.h>
#include "soccer.h"

using namespace std;
#define pb push_back
#define st first
#define nd second
typedef long long ll;
typedef long double ld;
const ll I = 1000LL * 1000LL * 1000LL * 1000LL * 1000LL * 1000LL;
const int II = 2 * 1000 * 1000 * 1000;
const ll M = 1000LL * 1000LL * 1000LL + 7LL;
const int N = 2'007;
int XDN;
int tab[N][N], il[N][N], nxt[N][N];
vector<pair<int, int>> ed[N * N * 4];

map<pair<pair<int, int>, pair<int, int>>, int> num;
pair<pair<int, int>, pair<int, int>> pos[N * N * 4];
int dp[N * N * 4], wch[N * N * 4];

int spt[N][N][11];

void Cnt(int n)
{
    for(int i = 1; i <= n; ++i)
        nxt[i][n + 1] = n + 1;
    for(int i = 1; i <= n; ++i)
        for(int j = n; j >= 1; --j)
        {
            nxt[i][j] = nxt[i][j + 1];
            il[i][j] = il[i][j + 1] + 1;
            if(tab[i][j] == 0) nxt[i][j] = j;
            else il[i][j] = 0;
            spt[i][j][0] = il[i][j];
        }
    for(int i = n; i >= 1; --i)
        for(int j = 1; j <= n; ++j)
            for(int l = 1; i + (1<<l) - 1 <= n; ++l)
                spt[i][j][l] = min(spt[i][j][l - 1], spt[i + (1<<(l - 1))][j][l - 1]);
}

int Min(int i1, int i2, int j)
{
    int d = (i2 - i1 + 1);
    int l = 31 - __builtin_clz(d);
    return min(spt[i1][j][l], spt[i2 - (1<<l) + 1][j][l]);
}

int FU(int i, int j, int x)
{
    int p = 1, k = i, s;
    while(p < k)
    {
        s = (p + k) / 2;
        if(Min(s, i, j) >= x)
            k = s;
        else
            p = s + 1;
    }
    return p;
}

int FD(int i, int j, int x)
{
    int p = i, k = XDN, s;
    while(p < k)
    {
        s = (p + k + 1) / 2;
        if(Min(i, s, j) >= x)
            p = s;
        else
            k = s - 1;
    }
    return p;
}

int GenG(int n)
{
    int cnt = 0, v;
    queue<int> q;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
        {
            if((j != 1 && tab[i][j - 1] == 0) || tab[i][j] == 1) continue;
            int u = FU(i, j, il[i][j]), d = FD(i, j, il[i][j]);
            pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + il[i][j] - 1));
            if(num.find(wsp) != num.end()) continue;
            ++cnt;
            num[wsp] = cnt; pos[cnt] = wsp;
            q.push(cnt);
            ed[0].pb(make_pair(cnt, (d - u + 1) * il[i][j]));
        }
    //cerr << "XDD\n";
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        //cerr << "Gen: " << v << " " << pos[v].st.st << " " << pos[v].st.nd << " " << pos[v].nd.st << " " << pos[v].nd.nd << "\n";
        for(int r = 0; r < 2; ++r)
        {
            //cerr << r << "\n";
            int i1 = pos[v].st.st, i2 = pos[v].nd.st;
            int cr = i1 - 1;
            int j = pos[v].st.nd;
            if(r == 1)
                cr = i2 + 1;

            j = nxt[cr][j];
            while(j <= pos[v].nd.nd && cr != 0 && cr != n + 1)
            {
                //cerr << "B " << j << "\n";
                int dis = min(il[cr][j], pos[v].nd.nd - j + 1);
                int u = FU(i1, j, dis), d = FD(i2, j, dis);
                pair<pair<int, int>, pair<int, int>> wsp = make_pair(make_pair(u, j), make_pair(d, j + dis - 1));
                //cerr << "Ne: " << wsp.st.st << " " << wsp.st.nd << " " << wsp.nd.st << " " << wsp.nd.nd << "\n";
                int ne;
                if(num.find(wsp) != num.end())
                    ne = num[wsp];
                else
                {
                    ++cnt; num[wsp] = cnt;
                    pos[cnt] = wsp;
                    ne = cnt;
                    q.push(cnt);
                }
                //cerr << ne << "\n";
                ed[v].pb(make_pair(ne, (i1 - u + d - i2) * dis));
                j += il[cr][j]; j = nxt[cr][j];
            }
            //cerr << "E\n";
        }
    }
    return cnt;
}

void Tsort(int n)
{
    int v;
    queue<int> q;
    for(int i = 0; i <= n; ++i)
        for(int j = 0; j < (int)ed[i].size(); ++j)
            ++wch[ed[i][j].st];
    for(int i = 0; i <= n; ++i)
        if(wch[i] == 0)
            q.push(i);
    while(q.size() > 0)
    {
        v = q.front(); q.pop();
        for(int i = 0; i < (int)ed[v].size(); ++i)
        {
            dp[ed[v][i].st] = max(dp[ed[v][i].st], dp[v] + ed[v][i].nd);
            --wch[ed[v][i].st];
            if(wch[ed[v][i].st] == 0)
                q.push(ed[v][i].st);
        }
    }
}

int biggest_stadium(int _N, vector<vector<int>> _F)
{
    int n = _N, m;
    XDN = n;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            tab[i][j] = _F[i - 1][j - 1];
    Cnt(n);
    m = GenG(n);
    Tsort(m);
    int ans = 0;
    for(int i = 1; i <= m; ++i)
        ans = max(ans, dp[i]);
        
    return ans;
}

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