oj.uz

Submission #991962

# Submission time Handle Problem Language Result Execution time Memory
991962 2024-06-03T13:01:40 Z phoenix Wall (IOI14_wall) C++17
100 / 100
 594 ms 77868 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int N = (1 << 21);
const int INF = 1e9;

int tr_min[2 * N];
int tr_max[2 * N];

void setpush(int v, int l, int r) {
  tr_min[v] = max(tr_min[v], l);
  tr_min[v] = min(tr_min[v], r);
  tr_max[v] = max(tr_max[v], l);
  tr_max[v] = min(tr_max[v], r);
}

void push(int v) {
  if (v >= N) return;
  setpush(2 * v, tr_min[v], tr_max[v]);
  setpush(2 * v + 1, tr_min[v], tr_max[v]);
}

void update(int ql, int qr, int lb, int rb, int l = 0, int r = N - 1, int v = 1) {
  if (r < ql || l > qr)
    return;
  if (ql <= l && r <= qr) {
    setpush(v, lb, rb);
    return;
  }
  push(v);
  int mid = (l + r) / 2;
  update(ql, qr, lb, rb, l, mid, 2 * v);
  update(ql, qr, lb, rb, mid + 1, r, 2 * v + 1);
  tr_min[v] = min(tr_min[2 * v], tr_min[2 * v + 1]);
  tr_max[v] = max(tr_max[2 * v], tr_max[2 * v + 1]);
}

int arr[N];
void construct(int l = 0, int r = N - 1, int v = 1) {
  if (l == r) {
    arr[l] = tr_min[v];
    return;
  }
  push(v);
  int mid = (l + r) / 2;
  construct(l, mid, 2 * v);
  construct(mid + 1, r, 2 * v + 1);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      update(left[i], right[i], height[i], INF);
    } else {
      update(left[i], right[i], 0, height[i]);
    }
  }
  construct();
  for (int i = 0; i < n; i++)
    finalHeight[i] = arr[i];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 41308 KB Output is correct
2 Correct 34 ms 41572 KB Output is correct
3 Correct 30 ms 41308 KB Output is correct
4 Correct 37 ms 41552 KB Output is correct
5 Correct 33 ms 41604 KB Output is correct
6 Correct 32 ms 41552 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 41300 KB Output is correct
2 Correct 363 ms 55000 KB Output is correct
3 Correct 202 ms 47196 KB Output is correct
4 Correct 442 ms 59476 KB Output is correct
5 Correct 300 ms 60500 KB Output is correct
6 Correct 312 ms 58860 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 41304 KB Output is correct
2 Correct 32 ms 41564 KB Output is correct
3 Correct 32 ms 41300 KB Output is correct
4 Correct 33 ms 41616 KB Output is correct
5 Correct 34 ms 41564 KB Output is correct
6 Correct 34 ms 41560 KB Output is correct
7 Correct 31 ms 41456 KB Output is correct
8 Correct 356 ms 54868 KB Output is correct
9 Correct 191 ms 48468 KB Output is correct
10 Correct 458 ms 59260 KB Output is correct
11 Correct 288 ms 60504 KB Output is correct
12 Correct 314 ms 58964 KB Output is correct
13 Correct 29 ms 41308 KB Output is correct
14 Correct 369 ms 54872 KB Output is correct
15 Correct 56 ms 42580 KB Output is correct
16 Correct 448 ms 59732 KB Output is correct
17 Correct 294 ms 58964 KB Output is correct
18 Correct 313 ms 59164 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 41300 KB Output is correct
2 Correct 41 ms 41556 KB Output is correct
3 Correct 34 ms 41404 KB Output is correct
4 Correct 37 ms 41684 KB Output is correct
5 Correct 35 ms 41480 KB Output is correct
6 Correct 38 ms 41592 KB Output is correct
7 Correct 31 ms 41300 KB Output is correct
8 Correct 433 ms 54868 KB Output is correct
9 Correct 196 ms 48512 KB Output is correct
10 Correct 481 ms 59452 KB Output is correct
11 Correct 319 ms 60348 KB Output is correct
12 Correct 337 ms 58740 KB Output is correct
13 Correct 30 ms 41308 KB Output is correct
14 Correct 351 ms 54984 KB Output is correct
15 Correct 53 ms 42596 KB Output is correct
16 Correct 497 ms 59512 KB Output is correct
17 Correct 334 ms 59164 KB Output is correct
18 Correct 290 ms 58924 KB Output is correct
19 Correct 576 ms 77628 KB Output is correct
20 Correct 559 ms 75348 KB Output is correct
21 Correct 546 ms 77624 KB Output is correct
22 Correct 517 ms 75328 KB Output is correct
23 Correct 573 ms 75204 KB Output is correct
24 Correct 564 ms 75364 KB Output is correct
25 Correct 594 ms 75164 KB Output is correct
26 Correct 564 ms 77820 KB Output is correct
27 Correct 548 ms 77868 KB Output is correct
28 Correct 529 ms 75092 KB Output is correct
29 Correct 577 ms 75348 KB Output is correct
30 Correct 532 ms 75348 KB Output is correct