제출 #1225016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1225016		abczz	축구 경기장 (IOI23_soccer)	C++20	6 / 100	747 ms	204228 KiB

soccer

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

using namespace std;

struct MonotoneQueue{
  vector <array<ll, 2>> st;
  void push_back(ll u, ll id) {
    while (!st.empty() && st.back()[0] <= u) st.pop_back();
    st.push_back({u, id});
  }
  void pop_back(ll u) {
    if (!st.empty() && st.back()[1] == u) st.pop_back();
  }
  ll query() {
    return st.empty() ? 0LL : st.back()[0];
  }
  void clear() {
    st.clear();
  }
}Q;
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));
  }
}ST;
ll dpR[2000][2000], dpL[2000][2000], nxR[2000][2000], nxL[2000][2000], ans[2000][2000];

void solve(int N, vector<vector<int>> F) {
  ST.init();
  for (int i=0; i<N; ++i) {
    ll p = -1;
    for (int j=0; j<N; ++j) {
      if (F[i][j]) p = j;
      nxL[i][j] = p;
    }
    p = N;
    for (int j=N-1; j>=0; --j) {
      if (F[i][j]) p = j;
      nxR[i][j] = p;
    }
  }
  ll u;
  for (ll i=0; i<N; ++i) {
    for (ll j=0; j<N; ++j) {
      dpR[i][j] = dpL[i][j] = (ll)-1e18;
      if (F[i][j]) continue;
      if (!i) dpR[i][j] = nxR[i][j]-j;
      else {
        if (!j || F[i][j-1]) {
          u = i-1;
          Q.clear();
          for (int k=j; k<nxR[i][j]; ++k) {
            if (F[i-1][k]) continue;
            if (k == j || F[i-1][k-1]) {
              if (nxR[i-1][k] <= nxR[i][j]) Q.push_back(dpR[i-1][k], k);
              else {
                Q.push_back(dpL[i-1][nxR[i][j]-1], k);
                break;
              }
            }
          }
        }
        dpR[i][j] = max(Q.query(), (u != -1 && !F[u][j] && nxR[u][j] <= nxR[i][j] ? dpR[u][j] : (ll)-1e18)) + (nxR[i][j]-j) * (i-u);
        Q.pop_back(j);
        if (j+1 != nxR[i][j] && Q.st.empty()) {
          u = ST.query(1, 0, N-1, j+1, nxR[i][j]-1);
          if (u != -1) {
            for (int k=j+1; k<nxR[i][j]; ++k) {
              if (F[u][k]) continue;
              if (k == j+1 || F[u][k-1]) {
                if (nxR[u][k] <= nxR[i][j]) Q.push_back(dpR[u][k], k);
                else {
                  Q.push_back(dpL[u][nxR[i][j]-1], k);
                  break;
                }
              }
            }
          }
        }
      }
    }
    for (int j=N-1; j>=0; --j) {
      if (F[i][j]) {
        ST.update(1, 0, N-1, j, i);
        continue;
      }
      if (!i) dpL[i][j] = j-nxL[i][j];
      else {
        if (j == N-1 || F[i][j+1]) {
          u = i-1;
          Q.clear();
          for (int k=j; k>nxL[i][j]; --k) {
            if (F[i-1][k]) continue;
            if (k == j || F[i-1][k+1]) {
              if (nxL[i-1][k] >= nxL[i][j]) Q.push_back(dpL[i-1][k], k);
              else {
                Q.push_back(dpR[i-1][nxL[i][j]+1], k);
                break;
              }
            }
          }
        }
        dpL[i][j] = max(Q.query(), (u != -1 && !F[u][j] && nxL[u][j] >= nxL[i][j] ? dpL[u][j] : (ll)-1e18)) + (j-nxL[i][j]) * (i-u);
        Q.pop_back(j);
        if (j-1 != nxL[i][j] && Q.st.empty()) {
          u = ST.query(1, 0, N-1, nxL[i][j]+1, j-1);
          if (u != -1) {
            for (int k=j-1; k>nxL[i][j]; --k) {
              if (F[u][k]) continue;
              if (k == j-1 || F[u][k+1]) {
                if (nxL[u][k] >= nxL[i][j]) Q.push_back(dpL[u][k], k);
                else {
                  Q.push_back(dpR[u][nxL[i][j]+1], k);
                  break;
                }
              }
            }
          }
        }
      }
    }
  }
}
int biggest_stadium(int N, std::vector<std::vector<int>> F)
{
  solve(N, F);
  for (int i=0; i<N; ++i) {
    for (int j=0; j<N; ++j) {
      ans[i][j] = dpR[i][j]-(nxR[i][j]-j);
    }
  }
  for (int i=0; i<N/2; ++i) {
    swap(F[i], F[N-1-i]);
  }
  solve(N, F);
  int f = 0;
  for (int i=0; i<N; ++i) {
    for (int j=0; j<N; ++j) {
      ans[i][j] += dpR[N-1-i][j];
      ans[i][j] = max(0LL, ans[i][j]);
      f = max(f, (int)ans[i][j]);
    }
  }
  return f;
}

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