oj.uz

Submission #492821

# Submission time Handle Problem Language Result Execution time Memory
492821 2021-12-09T04:38:08 Z boykut Wall (IOI14_wall) C++14
100 / 100
 1116 ms 86344 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

template <typename T>
class segment_tree {
private:
  struct node {
    T min, max;
  };
  int n;
  vector<node> t;
  void push(int v, int vl, int vr) {
    if (vl == vr) return;
    t[2 * v + 1].min = ::max(t[v].min, ::min(t[2 * v + 1].min, t[v].max));
    t[2 * v + 1].max = ::min(t[v].max, ::max(t[2 * v + 1].max, t[v].min));
    t[2 * v + 2].min = ::max(t[v].min, ::min(t[2 * v + 2].min, t[v].max));
    t[2 * v + 2].max = ::min(t[v].max, ::max(t[2 * v + 2].max, t[v].min));
    t[v].min = 0; t[v].max = LLONG_MAX;
  }
  T get(int i, int v, int vl, int vr) {
    push(v, vl, vr);
    if (vl == vr) {
      return t[v].min;
    } else {
      int vm = (vl + vr) / 2;
      if (i <= vm)
        return get(i, 2 * v + 1, vl, vm);
      else
        return get(i, 2 * v + 2, vm + 1, vr);
    }
  }
  void update(int l, int r, T x, int v, int vl, int vr, int type) {
    push(v, vl, vr);
    if (l > vr || vl > r)
      return;
    if (l <= vl && vr <= r) {
      if (type == 1) {
        t[v].min = ::max(t[v].min, x);
        t[v].max = ::max(t[v].max, x);
      } else {
        t[v].min = ::min(t[v].min, x);
        t[v].max = ::min(t[v].max, x);
      }
    } else {
      int vm = (vl + vr) / 2;
      update(l, r, x, 2 * v + 1, vl, vm, type);
      update(l, r, x, 2 * v + 2, vm + 1, vr, type);
    }
  }
public:
  segment_tree(int k) {
    n = 1; while (n < k) n <<= 1;
    t = vector<node> (2 * n - 1, {0, LLONG_MAX});
  }
  T get(int i) {
    return get(i, 0, 0, n - 1);
  }
  void update(int l, int r, T x, int type) {
    update(l, r, x, 0, 0, n - 1, type);
  }
};

void buildWall(int n, int k, int op[], int l[], int r[], int h[], int ans[]){
  segment_tree<long long> st(n);
  for (int i = 0; i < k; i++) {
      st.update(l[i], r[i], h[i], op[i]);
  }
  for (int i = 0; i < n; i++) {
    ans[i] = st.get(i);
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 4 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 10 ms 940 KB Output is correct
5 Correct 6 ms 972 KB Output is correct
6 Correct 6 ms 972 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 141 ms 12716 KB Output is correct
3 Correct 211 ms 8444 KB Output is correct
4 Correct 562 ms 17584 KB Output is correct
5 Correct 329 ms 17596 KB Output is correct
6 Correct 362 ms 17768 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 460 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 11 ms 972 KB Output is correct
5 Correct 8 ms 972 KB Output is correct
6 Correct 7 ms 972 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 132 ms 13192 KB Output is correct
9 Correct 243 ms 8320 KB Output is correct
10 Correct 570 ms 17728 KB Output is correct
11 Correct 340 ms 17864 KB Output is correct
12 Correct 306 ms 17840 KB Output is correct
13 Correct 1 ms 204 KB Output is correct
14 Correct 162 ms 13356 KB Output is correct
15 Correct 40 ms 2380 KB Output is correct
16 Correct 581 ms 17816 KB Output is correct
17 Correct 388 ms 17848 KB Output is correct
18 Correct 337 ms 17844 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 432 KB Output is correct
3 Correct 3 ms 332 KB Output is correct
4 Correct 12 ms 972 KB Output is correct
5 Correct 8 ms 972 KB Output is correct
6 Correct 8 ms 972 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 161 ms 13220 KB Output is correct
9 Correct 299 ms 8288 KB Output is correct
10 Correct 514 ms 17728 KB Output is correct
11 Correct 339 ms 17868 KB Output is correct
12 Correct 347 ms 17988 KB Output is correct
13 Correct 0 ms 204 KB Output is correct
14 Correct 127 ms 13392 KB Output is correct
15 Correct 35 ms 2372 KB Output is correct
16 Correct 611 ms 17728 KB Output is correct
17 Correct 310 ms 17852 KB Output is correct
18 Correct 320 ms 17844 KB Output is correct
19 Correct 1052 ms 86344 KB Output is correct
20 Correct 1047 ms 85272 KB Output is correct
21 Correct 1116 ms 85220 KB Output is correct
22 Correct 1050 ms 84784 KB Output is correct
23 Correct 1059 ms 84828 KB Output is correct
24 Correct 1028 ms 85204 KB Output is correct
25 Correct 1016 ms 85276 KB Output is correct
26 Correct 1089 ms 85384 KB Output is correct
27 Correct 1018 ms 84980 KB Output is correct
28 Correct 1020 ms 84888 KB Output is correct
29 Correct 1045 ms 85180 KB Output is correct
30 Correct 1008 ms 85172 KB Output is correct