oj.uz

Submission #917045

# Submission time Handle Problem Language Result Execution time Memory
917045 2024-01-27T04:37:51 Z rxlfd314 Wall (IOI14_wall) C++17
100 / 100
 701 ms 120660 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

#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)

struct ST {
  vt<int> st_max, st_min, lz;
  ST(int n) {
    st_max.resize(n << 2);
    st_min.resize(n << 2);
    lz.resize(n << 2, -1);
  }
  #define lc i << 1
  #define rc lc | 1
  void push(int i) {
    if (lz[i] < 0)
      return;
    st_max[lc] = st_max[rc] = st_min[lc] = st_min[rc] = lz[lc] = lz[rc] = lz[i];
    lz[i] = -1;
  }
  void pull(int i) {
    st_max[i] = max(st_max[lc], st_max[rc]);
    st_min[i] = min(st_min[lc], st_min[rc]);
  }
  void chmax(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st_max) >> 2;
    if (tl > qr || tr < ql || st_min[i] >= v)
      return;
    if (ql <= tl && tr <= qr && st_max[i] < v)
      st_max[i] = st_min[i] = lz[i] = v;
    else {
      push(i);
      int tm = tl + tr >> 1;
      chmax(ql, qr, v, lc, tl, tm);
      chmax(ql, qr, v, rc, tm+1, tr);
      pull(i);
    }
  }
  void chmin(int ql, int qr, int v, int i = 1, int tl = 0, int tr = -1) {
    if (tr < 0)
      tr += size(st_max) >> 2;
    if (tl > qr || tr < ql || st_max[i] <= v)
      return;
    if (ql <= tl && tr <= qr && st_min[i] > v)
      st_max[i] = st_min[i] = lz[i] = v;
    else {
      push(i);
      int tm = tl + tr >> 1;
      chmin(ql, qr, v, lc, tl, tm);
      chmin(ql, qr, v, rc, tm+1, tr);
      pull(i);
    }
  }
  int qry(int p, int i = 1, int tl = 0, int tr = -1) {
    tr += size(st_max) >> 2;
    while (tl < tr) {
      push(i);
      int tm = tl + tr >> 1;
      if (p <= tm)
        i = lc, tr = tm;
      else
        i = rc, tl = tm + 1;
    }
    return st_max[i];
  }
  #undef lc
  #undef rc
};

void buildWall(int N, int K, int op[], int left[], int right[], int height[], int finalHeight[]){
  ST st(N);
  FOR(i, 0, K-1) {
    if (op[i] == 1)
      st.chmax(left[i], right[i], height[i]);
    else
      st.chmin(left[i], right[i], height[i]);
  }
  FOR(i, 0, N-1)
    finalHeight[i] = st.qry(i);
}

Compilation message

wall.cpp: In member function 'void ST::chmax(int, int, int, int, int, int)':
wall.cpp:41:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
wall.cpp: In member function 'void ST::chmin(int, int, int, int, int, int)':
wall.cpp:56:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |       int tm = tl + tr >> 1;
      |                ~~~^~~~
wall.cpp: In member function 'int ST::qry(int, int, int, int)':
wall.cpp:66:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   66 |       int tm = tl + tr >> 1;
      |                ~~~^~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 125 ms 13908 KB Output is correct
3 Correct 59 ms 8276 KB Output is correct
4 Correct 141 ms 22868 KB Output is correct
5 Correct 150 ms 23368 KB Output is correct
6 Correct 183 ms 21812 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 112 ms 13888 KB Output is correct
9 Correct 60 ms 8276 KB Output is correct
10 Correct 146 ms 22824 KB Output is correct
11 Correct 151 ms 23384 KB Output is correct
12 Correct 171 ms 21808 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 112 ms 13904 KB Output is correct
15 Correct 22 ms 2152 KB Output is correct
16 Correct 355 ms 22828 KB Output is correct
17 Correct 258 ms 22340 KB Output is correct
18 Correct 252 ms 22136 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 ms 448 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 5 ms 1112 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 113 ms 13904 KB Output is correct
9 Correct 57 ms 8148 KB Output is correct
10 Correct 150 ms 22952 KB Output is correct
11 Correct 153 ms 23336 KB Output is correct
12 Correct 172 ms 21768 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 119 ms 13956 KB Output is correct
15 Correct 21 ms 2136 KB Output is correct
16 Correct 353 ms 22820 KB Output is correct
17 Correct 253 ms 22312 KB Output is correct
18 Correct 251 ms 22356 KB Output is correct
19 Correct 700 ms 120096 KB Output is correct
20 Correct 672 ms 120568 KB Output is correct
21 Correct 671 ms 120320 KB Output is correct
22 Correct 667 ms 120324 KB Output is correct
23 Correct 684 ms 120264 KB Output is correct
24 Correct 679 ms 120660 KB Output is correct
25 Correct 701 ms 120460 KB Output is correct
26 Correct 675 ms 120320 KB Output is correct
27 Correct 677 ms 120216 KB Output is correct
28 Correct 670 ms 120312 KB Output is correct
29 Correct 676 ms 120252 KB Output is correct
30 Correct 675 ms 120404 KB Output is correct