oj.uz

Submission #880319

# Submission time Handle Problem Language Result Execution time Memory
880319 2023-11-29T07:22:40 Z rxlfd314 Pyramid Base (IOI08_pyramid_base) C++17
100 / 100
 1029 ms 179012 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1884 KB Output is correct

Subtask #5
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 14428 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 141284 KB Output is correct
2 Correct 65 ms 141396 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 67 ms 141432 KB Output is correct
2 Correct 64 ms 141396 KB Output is correct

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 1432 KB Output is correct
2 Correct 52 ms 1788 KB Output is correct
3 Correct 51 ms 1796 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 188 ms 9552 KB Output is correct
2 Correct 281 ms 10604 KB Output is correct
3 Correct 209 ms 10364 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 247 ms 65224 KB Output is correct
2 Correct 85 ms 50596 KB Output is correct
3 Correct 149 ms 33528 KB Output is correct
4 Correct 619 ms 80052 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 426 ms 74420 KB Output is correct
2 Correct 681 ms 82444 KB Output is correct
3 Correct 157 ms 65484 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 277 ms 66228 KB Output is correct
2 Correct 885 ms 85000 KB Output is correct
3 Correct 924 ms 82956 KB Output is correct
4 Correct 923 ms 83052 KB Output is correct
5 Correct 887 ms 83312 KB Output is correct
6 Correct 122 ms 65996 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 524 ms 156652 KB Output is correct
2 Correct 260 ms 66900 KB Output is correct

Subtask #14
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 673 ms 163564 KB Output is correct
2 Correct 685 ms 160116 KB Output is correct
3 Correct 431 ms 119136 KB Output is correct

Subtask #15
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 862 ms 170204 KB Output is correct
2 Correct 1029 ms 168140 KB Output is correct
3 Correct 1020 ms 179012 KB Output is correct
4 Correct 902 ms 176984 KB Output is correct
5 Correct 606 ms 171936 KB Output is correct