oj.uz

Submission #1013108

# Submission time Handle Problem Language Result Execution time Memory
1013108 2024-07-03T07:54:10 Z aufan Wall (IOI14_wall) C++17
100 / 100
 901 ms 224672 KB 
#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;
const int INF = 1e9;
struct node {
  int val, lb, ub;
  int st, en;
  node *left, *right;
  void lazy() {
    left->val = max(left->val, lb);
    left->lb = max(left->lb, lb);
    left->ub = max(left->ub, lb);
    left->val = min(left->val, ub);
    left->lb = min(left->lb, ub);
    left->ub = min(left->ub, ub);
    right->val = max(right->val, lb);
    right->lb = max(right->lb, lb);
    right->ub = max(right->ub, lb);
    right->val = min(right->val, ub);
    right->lb = min(right->lb, ub);
    right->ub = min(right->ub, ub);
    lb = -INF;
    ub = INF;
  }
  void build(int start, int end) {
    st = start;
    en = end;
    lb = -INF;
    ub = INF;
    if (st == en) {
      val = lb = ub = 0;
      return;
    }
    int md = (st + en)/2;
    left = new node();
    right = new node();
    left->build(st, md);
    right->build(md + 1, en);
  }
  int query(int id) {
    if (st > id || en < id) return 0;
    if (st == en) return val;
    lazy();
    return left->query(id) + right->query(id);
  }
  void updatebounds(int lf, int rg, int x, int y) {
    if (st > rg || en < lf) return;
    if (lf <= st && en <= rg) {
      val = max(val, x);
      lb = max(lb, x);
      ub = max(ub, x);
      val = min(val, y);
      lb = min(lb, y);
      ub = min(ub, y);
      return;
    }
    lazy();
    left->updatebounds(lf, rg, x, y);
    right->updatebounds(lf, rg, x, y);
  }
} sg;
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  sg.build(0, n - 1);
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      sg.updatebounds(left[i], right[i], height[i], INF);
    } else if (op[i] == 2) {
      sg.updatebounds(left[i], right[i], -INF, height[i]);
    }
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = sg.query(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 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1472 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 5 ms 1628 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 80 ms 13908 KB Output is correct
3 Correct 132 ms 9132 KB Output is correct
4 Correct 375 ms 27732 KB Output is correct
5 Correct 212 ms 28688 KB Output is correct
6 Correct 202 ms 27296 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 496 KB Output is correct
4 Correct 5 ms 1576 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 5 ms 1624 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 79 ms 13888 KB Output is correct
9 Correct 122 ms 9128 KB Output is correct
10 Correct 429 ms 27824 KB Output is correct
11 Correct 210 ms 28848 KB Output is correct
12 Correct 200 ms 27216 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 82 ms 14032 KB Output is correct
15 Correct 23 ms 3152 KB Output is correct
16 Correct 379 ms 28240 KB Output is correct
17 Correct 223 ms 27480 KB Output is correct
18 Correct 199 ms 27480 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 564 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1628 KB Output is correct
5 Correct 5 ms 1628 KB Output is correct
6 Correct 5 ms 1628 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 95 ms 13844 KB Output is correct
9 Correct 126 ms 9100 KB Output is correct
10 Correct 357 ms 27728 KB Output is correct
11 Correct 224 ms 28756 KB Output is correct
12 Correct 207 ms 27216 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 80 ms 13908 KB Output is correct
15 Correct 23 ms 3156 KB Output is correct
16 Correct 387 ms 27924 KB Output is correct
17 Correct 214 ms 27284 KB Output is correct
18 Correct 234 ms 27476 KB Output is correct
19 Correct 871 ms 224564 KB Output is correct
20 Correct 901 ms 222076 KB Output is correct
21 Correct 886 ms 224480 KB Output is correct
22 Correct 883 ms 222132 KB Output is correct
23 Correct 802 ms 221980 KB Output is correct
24 Correct 815 ms 221972 KB Output is correct
25 Correct 833 ms 221924 KB Output is correct
26 Correct 853 ms 224524 KB Output is correct
27 Correct 856 ms 224672 KB Output is correct
28 Correct 858 ms 222300 KB Output is correct
29 Correct 823 ms 222012 KB Output is correct
30 Correct 835 ms 222176 KB Output is correct