oj.uz

Submission #722242

# Submission time Handle Problem Language Result Execution time Memory
722242 2023-04-11T15:40:13 Z joelgun14 Wall (IOI14_wall) C++17
100 / 100
 1325 ms 85996 KB 
#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int lim = 1 << 21;
struct segment_tree {
  int lazymax[2 * lim], lazymin[2 * lim], a[2 * lim];
  segment_tree() {
    memset(a, 0, sizeof(a));
    fill(lazymin, lazymin + 2 * lim, INT_MAX);
    memset(lazymax, 0, sizeof(lazymax));
  }
  void propagate(int nd, int cl, int cr) {
    if(cl == cr) {
      a[nd] = max(lazymax[nd], a[nd]);
      a[nd] = min(lazymin[nd], a[nd]);
    }
    else {
      lazymax[2 * nd] = min(lazymin[nd], max(lazymax[2 * nd], lazymax[nd]));
      lazymin[2 * nd] = max(min(lazymin[2 * nd], lazymin[nd]), lazymax[nd]);
      lazymax[2 * nd + 1] = min(lazymin[nd], max(lazymax[2 * nd + 1], lazymax[nd]));
      lazymin[2 * nd + 1] = max(min(lazymin[2 * nd + 1], lazymin[nd]), lazymax[nd]);
    }
    lazymax[nd] = 0, lazymin[nd] = INT_MAX;
  }
  void update_max(int nd, int cl, int cr, int l, int r, int val) {
    propagate(nd, cl, cr);
    if(cl >= l && cr <= r) {
      lazymax[nd] = max(lazymax[nd], val);
      lazymin[nd] = max(lazymin[nd], val);
      propagate(nd, cl, cr);
    }
    else if(cl > r || cr < l) {
      return;
    }
    else {
      int mid = (cl + cr) / 2;
      update_max(2 * nd, cl, mid, l, r, val);
      update_max(2 * nd + 1, mid + 1, cr, l, r, val);
    }
  }
  void update_min(int nd, int cl, int cr, int l, int r, int val) {
    propagate(nd, cl, cr);
    if(cl >= l && cr <= r) {
      lazymax[nd] = min(lazymax[nd], val);
      lazymin[nd] = min(lazymin[nd], val);
      propagate(nd, cl, cr);
    }
    else if(cl > r || cr < l) {
      return;
    }
    else {
      int mid = (cl + cr) / 2;
      update_min(2 * nd, cl, mid, l, r, val);
      update_min(2 * nd + 1, mid + 1, cr, l, r, val);
    }
  }
  int query(int nd, int cl, int cr, int idx) {
    propagate(nd, cl, cr);
    if(cl == cr) {
      return a[nd];
    }
    else {
      int mid = (cl + cr) / 2;
      if(idx <= mid)
        return query(2 * nd, cl, mid, idx);
      else
        return query(2 * nd + 1, mid + 1, cr, idx);
    }
  }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  segment_tree seg;
  //cout << "SUCCEED 1 " << endl;
  for(int i = 0; i < k; ++i) {
    //cout << i << endl;
    if(op[i] == 1) {
      // max
      seg.update_max(1, 0, lim - 1, left[i], right[i], height[i]);
    }
    else {
      seg.update_min(1, 0, lim - 1, left[i], right[i], height[i]);
    }
  }
  for(int i = 0; i < n; ++i)
    finalHeight[i] = seg.query(1, 0, lim - 1, i);
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 49416 KB Output is correct
2 Correct 33 ms 49616 KB Output is correct
3 Correct 31 ms 49492 KB Output is correct
4 Correct 41 ms 49668 KB Output is correct
5 Correct 40 ms 49760 KB Output is correct
6 Correct 42 ms 49740 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 49428 KB Output is correct
2 Correct 408 ms 57368 KB Output is correct
3 Correct 301 ms 52820 KB Output is correct
4 Correct 711 ms 67492 KB Output is correct
5 Correct 485 ms 68504 KB Output is correct
6 Correct 393 ms 66948 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 49492 KB Output is correct
2 Correct 33 ms 49612 KB Output is correct
3 Correct 37 ms 49496 KB Output is correct
4 Correct 36 ms 49644 KB Output is correct
5 Correct 35 ms 49764 KB Output is correct
6 Correct 33 ms 49756 KB Output is correct
7 Correct 36 ms 49484 KB Output is correct
8 Correct 548 ms 63184 KB Output is correct
9 Correct 325 ms 56632 KB Output is correct
10 Correct 660 ms 67488 KB Output is correct
11 Correct 488 ms 68580 KB Output is correct
12 Correct 441 ms 67128 KB Output is correct
13 Correct 37 ms 49524 KB Output is correct
14 Correct 419 ms 63088 KB Output is correct
15 Correct 69 ms 50636 KB Output is correct
16 Correct 763 ms 67764 KB Output is correct
17 Correct 500 ms 67172 KB Output is correct
18 Correct 483 ms 67336 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 49484 KB Output is correct
2 Correct 41 ms 49492 KB Output is correct
3 Correct 31 ms 49492 KB Output is correct
4 Correct 36 ms 49632 KB Output is correct
5 Correct 34 ms 49748 KB Output is correct
6 Correct 43 ms 49736 KB Output is correct
7 Correct 26 ms 49448 KB Output is correct
8 Correct 583 ms 63180 KB Output is correct
9 Correct 293 ms 56624 KB Output is correct
10 Correct 624 ms 67508 KB Output is correct
11 Correct 449 ms 68588 KB Output is correct
12 Correct 415 ms 66992 KB Output is correct
13 Correct 27 ms 49440 KB Output is correct
14 Correct 474 ms 63276 KB Output is correct
15 Correct 96 ms 50704 KB Output is correct
16 Correct 768 ms 67824 KB Output is correct
17 Correct 464 ms 67168 KB Output is correct
18 Correct 550 ms 67204 KB Output is correct
19 Correct 1224 ms 85996 KB Output is correct
20 Correct 1102 ms 83452 KB Output is correct
21 Correct 1299 ms 85824 KB Output is correct
22 Correct 1115 ms 83420 KB Output is correct
23 Correct 1325 ms 83548 KB Output is correct
24 Correct 1198 ms 83372 KB Output is correct
25 Correct 1277 ms 83340 KB Output is correct
26 Correct 1185 ms 85924 KB Output is correct
27 Correct 1193 ms 85952 KB Output is correct
28 Correct 1150 ms 83512 KB Output is correct
29 Correct 1200 ms 83316 KB Output is correct
30 Correct 1159 ms 83388 KB Output is correct