oj.uz

Submission #554674

# Submission time Handle Problem Language Result Execution time Memory
554674 2022-04-29T06:52:47 Z Soumya1 Wall (IOI14_wall) C++17
100 / 100
 773 ms 98168 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 2e6 + 5;
struct Node {
  int mx = -1e9, mn = 1e9;
  Node() { }
  Node(int a, int b) { mn = a, mx = b; }
} t[4 * mxN];
void push(int x, Node v) {
  if (t[x].mn >= v.mn && v.mn >= t[x].mx) {
    t[x].mn = v.mn;
  } else if (v.mn < t[x].mx) {
    t[x] = Node(v.mn, v.mn);
  }
  if (t[x].mn >= v.mx && v.mx >= t[x].mx) {
    t[x].mx = v.mx;
  } else if (v.mx > t[x].mn) {
    t[x] = Node(v.mx, v.mx);
  }
}
void propagate(int x, int lx, int rx) {
  if (lx == rx) return;
  push(x << 1, t[x]);
  push(x << 1 | 1, t[x]);
  t[x] = Node(1e9, -1e9);
}
void update(int x, int lx, int rx, int l, int r, Node v) {
  if (t[x].mx != -1e9 || t[x].mn != 1e9) propagate(x, lx, rx);
  if (l > rx || lx > r) return;
  if (l <= lx && r >= rx) {
    push(x, v);
    return;
  }
  int mx = (lx + rx) >> 1;
  update(x << 1, lx, mx, l, r, v);
  update(x << 1 | 1, mx + 1, rx, l, r, v);
}
int query(int x, int lx, int rx, int i) {
  if (t[x].mx != -1e9 || t[x].mn != 1e9) propagate(x, lx, rx);
  if (lx == rx) {
    return max(t[x].mx, min(t[x].mn, 0));
  }
  int mx = (lx + rx) >> 1;
  if (i <= mx) return query(x << 1, lx, mx, i);
  return query(x << 1 | 1, mx + 1, rx, i);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i = 0; i < k; i++) {
    Node v = Node(1e9, height[i]);
    if (op[i] == 2) v = Node(height[i], -1e9);
    update(1, 1, n, left[i] + 1, right[i] + 1, v);
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = query(1, 1, n, i + 1);
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 62928 KB Output is correct
2 Correct 30 ms 62980 KB Output is correct
3 Correct 29 ms 62884 KB Output is correct
4 Correct 35 ms 63188 KB Output is correct
5 Correct 33 ms 63116 KB Output is correct
6 Correct 33 ms 63144 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62876 KB Output is correct
2 Correct 162 ms 76468 KB Output is correct
3 Correct 231 ms 70016 KB Output is correct
4 Correct 663 ms 80900 KB Output is correct
5 Correct 291 ms 80388 KB Output is correct
6 Correct 257 ms 80324 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 62848 KB Output is correct
2 Correct 31 ms 62936 KB Output is correct
3 Correct 31 ms 62928 KB Output is correct
4 Correct 38 ms 63112 KB Output is correct
5 Correct 33 ms 63052 KB Output is correct
6 Correct 34 ms 63188 KB Output is correct
7 Correct 29 ms 62880 KB Output is correct
8 Correct 192 ms 76548 KB Output is correct
9 Correct 240 ms 70024 KB Output is correct
10 Correct 674 ms 80892 KB Output is correct
11 Correct 279 ms 80508 KB Output is correct
12 Correct 295 ms 80452 KB Output is correct
13 Correct 30 ms 62804 KB Output is correct
14 Correct 163 ms 76472 KB Output is correct
15 Correct 81 ms 64080 KB Output is correct
16 Correct 773 ms 80176 KB Output is correct
17 Correct 335 ms 80484 KB Output is correct
18 Correct 294 ms 80596 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 62804 KB Output is correct
2 Correct 34 ms 62952 KB Output is correct
3 Correct 39 ms 62924 KB Output is correct
4 Correct 39 ms 63052 KB Output is correct
5 Correct 35 ms 63036 KB Output is correct
6 Correct 38 ms 63104 KB Output is correct
7 Correct 31 ms 62912 KB Output is correct
8 Correct 178 ms 76500 KB Output is correct
9 Correct 239 ms 70028 KB Output is correct
10 Correct 643 ms 80968 KB Output is correct
11 Correct 264 ms 80456 KB Output is correct
12 Correct 287 ms 80440 KB Output is correct
13 Correct 30 ms 62852 KB Output is correct
14 Correct 167 ms 76496 KB Output is correct
15 Correct 71 ms 64076 KB Output is correct
16 Correct 756 ms 80476 KB Output is correct
17 Correct 278 ms 80588 KB Output is correct
18 Correct 308 ms 80572 KB Output is correct
19 Correct 766 ms 97972 KB Output is correct
20 Correct 754 ms 95440 KB Output is correct
21 Correct 758 ms 97780 KB Output is correct
22 Correct 729 ms 95348 KB Output is correct
23 Correct 714 ms 95472 KB Output is correct
24 Correct 755 ms 95496 KB Output is correct
25 Correct 732 ms 95380 KB Output is correct
26 Correct 735 ms 98168 KB Output is correct
27 Correct 740 ms 98120 KB Output is correct
28 Correct 737 ms 95472 KB Output is correct
29 Correct 724 ms 95692 KB Output is correct
30 Correct 747 ms 95692 KB Output is correct