Submission #1226318

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226318		abczz	Soccer Stadium (IOI23_soccer)	C++20	70 / 100	4633 ms	1255692 KiB

soccer

#include "soccer.h"
#include <iostream>
#include <vector>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

struct LineContainer{
  struct Line{
    ll m, c;
    ll val(ll x) { return m*x+c; }
  };
  vector <Line> st;
  void push_back(Line cur) {
    while (!st.empty()) {
      if (st.back().m == cur.m) {
        if (st.back().c >= cur.c) return;
        st.pop_back();
      }
      else if (st.size() > 1) {
        auto u = st.back();
        auto v = st[st.size()-2];
        if ((u.c-v.c)*(u.m-cur.m) <= (cur.c-u.c)*(v.m-u.m)) st.pop_back();
        else break;
      }
      else break;
    }
    st.push_back(cur);
  }
  ll query(ll x) {
    if (st.empty()) return 0LL;
    else if (st.size() == 1) return st.back().val(x);
    ll l = 0, r = st.size()-2, mid;
    while (l < r) {
      mid = (l+r)/2;
      if (st[mid].val(x) >= st[mid+1].val(x)) r = mid;
      else l = mid+1;
    }
    return max(st[l].val(x), st.back().val(x));
  }
  void clear() {
    st.clear();
  }
}L;
struct LineSegTree{
  LineContainer st[8000];
  void update(ll id, ll l, ll r, ll q, LineContainer::Line cur) {
    st[id].push_back(cur);
    if (l == r) return;
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, cur);
    else update(id*2+1, mid+1, r, q, cur);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr, ll x) {
    if (qr < l || r < ql) return 0LL;
    else if (ql <= l && r <= qr) return st[id].query(x);
    ll mid = (l+r)/2;
    return max(query(id*2, l, mid, ql, qr, x), query(id*2+1, mid+1, r, ql, qr, x));
  }
}LST[2000];
struct SegTree{
  ll st[8000];
  void init() {
    for (int i=0; i<8000; ++i) st[i] = -1;
  }
  void update(ll id, ll l, ll r, ll q, ll w) {
    if (l == r) {
      st[id] = w;
      return;
    }
    ll mid = (l+r)/2;
    if (q <= mid) update(id*2, l, mid, q, w);
    else update(id*2+1, mid+1, r, q, w);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return -1;
    else if (ql <= l && r <= qr) return st[id];
    ll mid = (l+r)/2;
    return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
  }
}blocks[2000], ST;
vector <array<ll, 6> > V;
ll dpR[2000][2000], dpL[2000][2000], dir[2][2][2000][2000], ans[2000][2000];
array <ll, 2> nxR[2000][2000], nxL[2000][2000];

int solve(int N, vector<vector<int>> F) {
  int f = 0;
  ST.init();
  for (int i=0; i<N; ++i) {
    array<ll, 2> p = {-1, -1};
    for (int j=0; j<N; ++j) {
      p[F[i][j]] = j;
      nxL[i][j] = p;
    }
    p = {N, N};
    for (int j=N-1; j>=0; --j) {
      p[F[i][j]] = j;
      nxR[i][j] = p;
    }
  }
  for (int i=0; i<N; ++i) {
    blocks[i].init();
    for (int j=0; j<N; ++j) {
      dpR[i][j] = dpL[i][j] = (ll)-1e18;
      if (F[i][j]) {
        ST.update(1, 0, N-1, j, i);
        continue;
      }
      dir[0][0][i][j] = ST.query(1, 0, N-1, j, nxR[i][j][1]-1)+1;
      dir[1][0][i][j] = ST.query(1, 0, N-1, nxL[i][j][1]+1, j)+1;
    }
  }
  ST.init();
  for (int i=N-1; i>=0; --i) {
    for (int j=0; j<N; ++j) {
      if (F[i][j]) {
        ST.update(1, 0, N-1, j, N-1-i);
        continue;
      }
      dir[0][1][i][j] = N-1-ST.query(1, 0, N-1, j, nxR[i][j][1]-1)-1;
      dir[1][1][i][j] = N-1-ST.query(1, 0, N-1, nxL[i][j][1]+1, j)-1;
      V.push_back({i, j, j, 0, dir[0][0][i][j], dir[0][1][i][j]});
      V.push_back({i, nxL[i][j][1]+1, j, 1, dir[1][0][i][j], dir[1][1][i][j]});
    }
  }
  sort(V.begin(), V.end(), [](auto a, auto b) {
    return (!a[3] ? nxR[a[0]][a[1]][1]-1 : a[2])-a[1] < (!b[3] ? nxR[b[0]][b[1]][1]-1 : b[2])-b[1];
  });
  for (auto [i, a, b, ty, l, r] : V) {
    auto j = (!ty ? nxR[i][a][1]-1 : b);
    ll cur = 0;
    if (l) {
      auto u = nxR[l-1][a][1];
      auto v = nxL[l-1][j][1];
      if (u < N-1 && v > 0) {
        u = nxR[l-1][u+1][0];
        v = nxL[l-1][v-1][0];
        if (u <= v) cur = max(cur, LST[l-1].query(1, 0, N-1, u, v, r-l+1));
      }
      if (!F[l-1][a]) cur = max(cur, dpR[l-1][a] - (r-l+1) * (nxR[l-1][a][1]-a));
      if (!F[l-1][j]) cur = max(cur, dpL[l-1][j] - (r-l+1) * (j-nxL[l-1][j][1]));
    }
    if (r != N-1) {
      auto u = nxR[r+1][a][1];
      auto v = nxL[r+1][j][1];
      if (u < N-1 && v > 0) {
        u = nxR[r+1][u+1][0];
        v = nxL[r+1][v-1][0];
        if (u <= v) cur = max(cur, LST[r+1].query(1, 0, N-1, u, v, r-l+1));
      }
      if (!F[r+1][a]) cur = max(cur, dpR[r+1][a] - (r-l+1) * (nxR[r+1][a][1]-a));
      if (!F[r+1][j]) cur = max(cur, dpL[r+1][j] - (r-l+1) * (j-nxL[r+1][j][1]));
    }
    if (!ty) dpR[i][b] = cur + (j-a+1) * (r-l+1), f = max(f, (int)dpR[i][b]);
    else dpL[i][b] = cur + (j-a+1) * (r-l+1);
    if (!ty && (!b || F[i][b-1])) {
      LST[i].update(1, 0, N-1, j, LineContainer::Line{-(j-a+1), dpR[i][b]});
    }
  }
  return f;
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
  return solve(N, F);
}

• 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: 0 / 30