Submission #880319

#	Time	Username	Problem	Language	Result	Execution time	Memory
880319		rxlfd314	Pyramid Base (IOI08_pyramid_base)	C++17	100 / 100	1029 ms	179012 KiB

pyramid_base

#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using ari4 = array<int, 4>;

#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)

#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)

#define chmax(a, b) (a = a > (b) ? a : (b))
#define chmin(a, b) (a = a < (b) ? a : (b))

struct ST1 {
  vt<int> st, lz;
  ST1(int n) {
    st.resize(n<<2);
    lz.resize(n<<2);
  }
  #define lc i << 1
  #define rc i << 1 | 1
  void push(int i) {
    if (!lz[i])
      return;
    st[lc] += lz[i], st[rc] += lz[i];
    lz[lc] += lz[i], lz[rc] += lz[i];
    lz[i] = 0;
  }
  void radd(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st) >> 2;
    if (tl > qr || tr < ql)
      return;
    if (ql <= tl && tr <= qr)
      st[i] += v, lz[i] += v;
    else {
      push(i);
      int tm = tl + tr >> 1;
      radd(ql, qr, v, lc, tl, tm);
      radd(ql, qr, v, rc, tm+1, tr);
      st[i] = min(st[lc], st[rc]);
    }
  }
  #undef lc
  #undef rc
};

struct ST2 {
  vt<array<int, 5>> st;
  vt<int> lz;
  ST2(int n) {
    st.resize(n<<2);
    lz.resize(n<<2);
    build();
  }
  #define lc i << 1
  #define rc i << 1 | 1
  array<int, 5> merge(array<int, 5> &a, array<int, 5> &b) {
    // value, prefix, suffix, length, answer
    if (a[0] < b[0])
      return {a[0], a[1], 0, a[3] + b[3], a[4]};
    if (a[0] > b[0])
      return {b[0], 0, b[2], a[3] + b[3], b[4]};
    return {a[0], a[1] + (a[1] == a[3]) * b[1], b[2] + (b[2] == b[3]) * a[2], a[3] + b[3], max({a[4], b[4], a[2] + b[1]})};
  }
  void build(int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st) >> 2;
    st[i] = {0, 1, 1, 1, 1};
    if (tl == tr)
      return;
    int tm = tl + tr >> 1;
    build(lc, tl, tm);
    build(rc, tm+1, tr);
    st[i] = merge(st[lc], st[rc]);
  }
  void push(int i) {
    if (!lz[i])
      return;
    st[lc][0] += lz[i], st[rc][0] += lz[i];
    lz[lc] += lz[i], lz[rc] += lz[i];
    lz[i] = 0;
  }
  void radd(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st) >> 2;
    if (tl > qr || tr < ql)
      return;
    if (ql <= tl && tr <= qr)
      lz[i] += v, st[i][0] += v;
    else {
      push(i);
      int tm = tl + tr >> 1;
      radd(ql, qr, v, lc, tl, tm);
      radd(ql, qr, v, rc, tm+1, tr);
      st[i] = merge(st[lc], st[rc]);
    }
  }
  #undef lc
  #undef rc
};

signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int R, C, B, N;
  cin >> R >> C >> B >> N;
  int P[N], Q[N], X[N], Y[N], V[N];
  vt<ari2> ins[R+1], rem[R+1];
  FOR(i, 0, N-1) {
    int &a = P[i], &b = Q[i], &c = X[i], &d = Y[i], &v = V[i];
    cin >> a >> b >> c >> d >> v;
    ins[--a].push_back({--b, --d});
    rem[--c+1].push_back({b, d});
  }
  if (B) {
    int lo = 0, hi = min(R, C);
    while (lo < hi) {
      int mid = lo + hi + 1 >> 1;
      vt<ari4> evs; 
      FOR(i, 0, N-1) {
        evs.push_back({P[i], max(Q[i]-mid+1, 0), min(C-mid, Y[i]), V[i]});
        if (X[i] + mid < R)
          evs.push_back({X[i]+mid, max(Q[i]-mid+1, 0), min(C-mid, Y[i]), -V[i]});
      }
      sort(all(evs));
      ST1 st(C-mid+1);
      bool can = false;
      int j = 0;
      FOR(i, mid-1, R-1) {
        for (; j < size(evs) && evs[j][0] <= i; j++)
          st.radd(evs[j][1], evs[j][2], evs[j][3]);
        can |= st.st[1] <= B;
      }
      if (can)
        lo = mid;
      else
        hi = mid - 1;
    }
    cout << lo << '\n';
  } else {
    int j = 0, ans = 0;
    ST2 st(C);
    FOR(i, 0, R-1) {
      for (auto &[l, r] : rem[i])
        st.radd(l, r, -1);
      while (j <= R && j - i <= st.st[1][4] * !st.st[1][0]) {
        for (auto &[l, r] : ins[j])
          st.radd(l, r, 1);
        chmax(ans, j - i);
        j++;
      }
    }
    cout << ans << '\n';
  }
}

Compilation message (stderr)

pyramid_base.cpp: In member function 'void ST1::radd(int, int, int, int, int, int)':
pyramid_base.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   42 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
pyramid_base.cpp: In member function 'void ST2::build(int, int, int)':
pyramid_base.cpp:76:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   76 |     int tm = tl + tr >> 1;
      |              ~~~^~~~
pyramid_base.cpp: In member function 'void ST2::radd(int, int, int, int, int, int)':
pyramid_base.cpp:97:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   97 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
pyramid_base.cpp: In function 'int main()':
pyramid_base.cpp:123:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  123 |       int mid = lo + hi + 1 >> 1;
      |                 ~~~~~~~~^~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 5 / 5
• Subtask 4: 5 / 5
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 7 / 7
• Subtask 9: 7 / 7
• Subtask 10: 7 / 7
• Subtask 11: 7 / 7
• Subtask 12: 7 / 7
• Subtask 13: 10 / 10
• Subtask 14: 10 / 10
• Subtask 15: 10 / 10