Submission #840861

#	Time	Username	Problem	Language	Result	Execution time	Memory
840861		PurpleCrayon	Soccer Stadium (IOI23_soccer)	C++17	100 / 100	4399 ms	1151512 KiB

soccer

#include "soccer.h"
#include <bits/stdc++.h>
using namespace std;
 
#define ar array
#define sz(v) int(v.size())
typedef long long ll;
const int INF = 1e9+10;
const int M = 2e3+10, L = 12;
 
struct Sparse {
    int sparse[L][M];
    Sparse() {}
    Sparse(vector<int>& v) {
        int n = v.size();
        for (int j = 0; j < n; j++) sparse[0][j] = v[j];
        for (int i = 1; (1 << i) <= n; i++) {
            for (int j = 0; j + (1 << i) <= n; j++) {
                sparse[i][j] = min(sparse[i-1][j], sparse[i-1][j + (1 << (i-1))]);
            }
        }
    }
 
    inline int qry(int l, int r) {
        int b = 31 - __builtin_clz(r - l + 1);
        return min(sparse[b][l], sparse[b][r - (1 << b) + 1]);
    }
} ones[M], twos[M];
 
int get_cost(int i, int l, int r) {
    return max(0, ones[i].qry(l, r) + twos[i].qry(l, r) - 1);
}

int cnt_lr[M][M], cnt_l[M][M], cnt_r[M][M];
int store_up[M][M], store_down[M][M];
basic_string<pair<int, int>> impl[M][M], impr[M][M], has[M][M];
int dp[2 * M * M];
ar<int, 3> all[2 * M * M];
 
int biggest_stadium(int N, std::vector<std::vector<int>> F) {
    for (int j = 0; j < N; j++) {
        int one = 0;
        for (int i = 0; i < N; i++) {
            one = F[i][j] ? 0 : one + 1;
            store_up[i][j] = one;
        }

        int two = 0;
        for (int i = N-1; i >= 0; i--) {
            two = F[i][j] ? 0 : two + 1;
            store_down[i][j] = two;
        }
    }

    for (int i = 0; i < N; i++) {
        vector<int> up(N), down(N);
        for (int j = 0; j < N; j++) {
            up[j] = store_up[i][j], down[j] = store_down[i][j];
        }
 
        ones[i] = Sparse(up), twos[i] = Sparse(down);
    }
 
    int id = 0;
    auto add_imp = [&](int i, int l, int r) {
        all[id++] = {i, l, r};
        cnt_lr[l][r]++;
        cnt_l[i][l]++, cnt_r[i][r]++;
    };
 
    for (int i = 0; i < N; i++) {
        vector<int> blocks{-1};
        for (int j = 0; j < N; j++) if (F[i][j])
            blocks.push_back(j);
        
        blocks.push_back(N);
 
        for (int j = 1; j < sz(blocks); j++) if (blocks[j] > blocks[j-1] + 1) {
            int l = blocks[j-1]+1, r = blocks[j]-1;
            for (int k = l; k <= r; k++) {
                add_imp(i, k, r);
                if (k != r) add_imp(i, l, k);
            }
        }
    }
 
    for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
        impl[i][j].reserve(cnt_l[i][j]), impr[i][j].reserve(cnt_r[i][j]);
        has[i][j].reserve(cnt_lr[i][j]);
    }

    for (int me = 0; me < id; me++) {
        auto [i, l, r] = all[me];
        has[l][r].push_back(make_pair(i, me));
    }

    for (int l = 0; l < N; l++) {
        for (int r = 0; r < N; r++) {
            for (auto [i, me] : has[l][r]) {
                impl[i][l].push_back(make_pair(r, me));
            }
        }
    }

    for (int r = 0; r < N; r++) {
        for (int l = 0; l < N; l++) {
            for (auto [i, me] : has[l][r]) {
                impr[i][r].push_back(make_pair(l, me));
            }
        }
    }

    auto upd = [&](int ni, int l, int r, int x, int cur_cost) {
        if (ni < 0 || ni >= N) return;
        int nl = upper_bound(impr[ni][r].begin(), impr[ni][r].end(), make_pair(l, M)) - impr[ni][r].begin();
        if (nl < sz(impr[ni][r])) {
            int id = impr[ni][r][nl].second;
            nl = impr[ni][r][nl].first;
            dp[id] = max(dp[id], x + (get_cost(ni, nl, r) - cur_cost) * (r - nl + 1));
        }
 
        int nr = lower_bound(impl[ni][l].begin(), impl[ni][l].end(), make_pair(r, -1)) - impl[ni][l].begin() - 1;
        if (nr >= 0) {
            int id = impl[ni][l][nr].second;
            nr = impl[ni][l][nr].first;
            dp[id] = max(dp[id], x + (get_cost(ni, l, nr) - cur_cost) * (nr - l + 1));
        }
    };
 
    for (int l = 0; l < N; l++) {
        for (int r = N-1; r >= 0; r--) {
            for (auto [i, id] : has[l][r]) {
                int cur_cost = get_cost(i, l, r);
                int store = dp[id] = max(dp[id], cur_cost * (r - l + 1));
 
                int top = i - ones[i].qry(l, r);
                int bot = i + twos[i].qry(l, r);
                upd(i, l, r, store, cur_cost);
                upd(top, l, r, store, cur_cost);
                upd(bot, l, r, store, cur_cost);
            }
        }
    }
 
    int ans = 0;
    for (auto& x : dp) ans = max(ans, x);
    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