oj.uz

Submission #1018813

# Submission time Handle Problem Language Result Execution time Memory
1018813 2024-07-10T09:59:52 Z NeroZein Wall (IOI14_wall) C++17
100 / 100
 969 ms 68164 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std; 

const int N = 2e6 + 6;

int mn[N * 2], mx[N * 2];

void build(int nd, int l, int r) {
  if (l == r) {
    return; 
  }
  mn[nd] = N; 
  mx[nd] = 0;
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  build(nd + 1, l, mid);
  build(rs, mid + 1, r); 
}

void push(int nd, int l, int r) {
  if (l == r) return;
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  for (int i : {nd + 1, rs}) {
    mx[i] = max(mx[i], mx[nd]);
    mn[i] = max(mn[i], mx[nd]);
    mx[i] = min(mx[i], mn[nd]);
    mn[i] = min(mn[i], mn[nd]); 
  }
  mn[nd] = N; mx[nd] = 0; 
}

void upd(int nd, int l, int r, int s, int e, int v, bool maximize) {
  push(nd, l, r); 
  if (l >= s && r <= e) {
    if (maximize) {
      mx[nd] = max(mx[nd], v);
      mn[nd] = max(mn[nd], v); 
    } else {
      mx[nd] = min(mx[nd], v);
      mn[nd] = min(mn[nd], v);
    }
    push(nd, l, r);
    return;
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (mid >= e) {
    upd(nd + 1, l, mid, s, e, v, maximize);
  } else {
    if (mid < s) {
      upd(rs, mid + 1, r, s, e, v, maximize);       
    } else {
      upd(nd + 1, l, mid, s, e, v, maximize);
      upd(rs, mid + 1, r, s, e, v, maximize);             
    }
  }
}

int qry(int nd, int l, int r, int p) {
  push(nd, l, r); 
  if (l == r) {
    return mx[nd];
  }
  int mid = (l + r) >> 1;
  int rs = nd + ((mid - l + 1) << 1);
  if (p <= mid) {
    return qry(nd + 1, l, mid, p);
  } else {
    return qry(rs, mid + 1, r, p); 
  }
}

void buildWall(int n, int q, int op[], int l[], int r[], int v[], int finalHeight[]) {
  build(0, 0, n - 1); 
  for (int i = 0; i < q; ++i) {
    upd(0, 0, n - 1, l[i], r[i], v[i], op[i] % 2); 
  }
  for (int i = 0; i < n; ++i) {
    finalHeight[i] = qry(0, 0, n - 1, i);
  }
  return;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 83 ms 13908 KB Output is correct
3 Correct 146 ms 9556 KB Output is correct
4 Correct 429 ms 20052 KB Output is correct
5 Correct 217 ms 22464 KB Output is correct
6 Correct 245 ms 22020 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 2 ms 584 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 5 ms 2652 KB Output is correct
5 Correct 5 ms 2652 KB Output is correct
6 Correct 5 ms 2652 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 81 ms 13868 KB Output is correct
9 Correct 153 ms 9552 KB Output is correct
10 Correct 426 ms 22632 KB Output is correct
11 Correct 223 ms 23632 KB Output is correct
12 Correct 213 ms 22204 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 84 ms 13868 KB Output is correct
15 Correct 25 ms 3672 KB Output is correct
16 Correct 428 ms 20240 KB Output is correct
17 Correct 234 ms 20816 KB Output is correct
18 Correct 243 ms 20820 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 6 ms 2908 KB Output is correct
5 Correct 6 ms 860 KB Output is correct
6 Correct 5 ms 856 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 95 ms 13908 KB Output is correct
9 Correct 244 ms 7760 KB Output is correct
10 Correct 476 ms 19992 KB Output is correct
11 Correct 220 ms 22352 KB Output is correct
12 Correct 230 ms 22228 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 92 ms 13900 KB Output is correct
15 Correct 32 ms 3692 KB Output is correct
16 Correct 455 ms 21356 KB Output is correct
17 Correct 226 ms 22384 KB Output is correct
18 Correct 221 ms 22352 KB Output is correct
19 Correct 934 ms 67932 KB Output is correct
20 Correct 928 ms 65580 KB Output is correct
21 Correct 950 ms 68116 KB Output is correct
22 Correct 969 ms 65624 KB Output is correct
23 Correct 931 ms 65392 KB Output is correct
24 Correct 906 ms 65616 KB Output is correct
25 Correct 911 ms 65616 KB Output is correct
26 Correct 896 ms 68164 KB Output is correct
27 Correct 871 ms 67924 KB Output is correct
28 Correct 909 ms 65616 KB Output is correct
29 Correct 925 ms 65620 KB Output is correct
30 Correct 945 ms 65616 KB Output is correct