oj.uz

Submission #880307

# Submission time Handle Problem Language Result Execution time Memory
880307 2023-11-29T06:53:45 Z rxlfd314 Pyramid Base (IOI08_pyramid_base) C++17
35 / 100
 949 ms 170072 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 < b)
      return {a[0], a[1], 0, a[3] + b[3], max(a[4], b[4])};
    if (a > b)
      return {b[0], 0, b[2], a[3] + b[3], max(a[4], 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], rem[R];
  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);
        j++;
        chmax(ans, j - i);
      }
    }
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 1884 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 9 ms 14428 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 75 ms 141360 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 72 ms 141392 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 1748 KB Output is correct
2 Correct 55 ms 1956 KB Output is correct
3 Correct 44 ms 1796 KB Output is correct

Subtask #9
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 215 ms 9524 KB Output is correct
2 Correct 277 ms 10484 KB Output is correct
3 Correct 209 ms 10244 KB Output is correct

Subtask #10
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 65232 KB Output is correct
2 Correct 92 ms 50896 KB Output is correct
3 Correct 152 ms 35556 KB Output is correct
4 Correct 674 ms 79824 KB Output is correct

Subtask #11
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 74668 KB Output is correct
2 Correct 704 ms 82564 KB Output is correct
3 Correct 154 ms 65484 KB Output is correct

Subtask #12
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 309 ms 66268 KB Output is correct
2 Correct 919 ms 83012 KB Output is correct
3 Correct 930 ms 83188 KB Output is correct
4 Correct 926 ms 82944 KB Output is correct
5 Correct 949 ms 83308 KB Output is correct
6 Correct 122 ms 66000 KB Output is correct

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 603 ms 156664 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #14
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 755 ms 163568 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #15
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 906 ms 170072 KB Output isn't correct
2 Halted 0 ms 0 KB -