oj.uz

Submission #680387

# Submission time Handle Problem Language Result Execution time Memory
680387 2023-01-10T17:16:37 Z MattTheNub Wall (IOI14_wall) C++17
100 / 100
 661 ms 59468 KB 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
#define dbg(x) cerr << "[" << __LINE__ << "] " << #x << " = " << (x) << '\n';

template <class T> using v = vector<T>;

struct Node {
  int dec, inc;

  // dec = 0
  // inc = 9
  // -> dec=9, inc=9
  //
  void cinc(int val) {
    if (dec < val) {
      dec = val;
    }
    inc = max(inc, val);
  }
  void cdec(int val) {
    if (inc > val) {
      inc = val;
    }
    dec = min(dec, val);
  }
};

// h=0, increase to 2, decrease to 1 -> 1
// h=0, decrease to 1, increase to 2 -> 2
// dec>=inc holds
// order matters

template <class T> struct Seg {
  // TODO: implement
  const T ID = {INT_MAX, -1}; // comb(ID,b) = b
  T comb(T a, T b) { return {INT_MAX, -1}; }

  int n;
  v<T> seg;
  void init(int _n) {
    n = _n;
    seg.assign(2 * n, ID);
  }
  void push(int p) {
    if (seg[p].dec != INT_MAX) {
      seg[2 * p].cdec(seg[p].dec);
      seg[2 * p + 1].cdec(seg[p].dec);
      seg[p].dec = INT_MAX;
    }
    if (seg[p].inc != -1) {
      seg[2 * p].cinc(seg[p].inc);
      seg[2 * p + 1].cinc(seg[p].inc);
      seg[p].inc = -1;
    }
  }
  // void pull(int p) { seg[p] = comb(seg[2 * p], seg[2 * p + 1]); }
  void upd(int p, T val) { // set val at position p
    seg[p += n] = val;
    // for (p /= 2; p; p /= 2)
    // pull(p);
  }
  void inc(int l, int r, int val) { inc(1, 0, n - 1, l, r, val); }
  void inc(int p, int l, int r, int a, int b, int v) {
    if (a > r || b < l)
      return;
    if (a <= l && r <= b) {
      seg[p].cinc(v);
      return;
    }
    int mid = (l + r) / 2;
    push(p);
    inc(2 * p, l, mid, a, b, v);
    inc(2 * p + 1, mid + 1, r, a, b, v);
    // pull(p);
  }

  void dec(int l, int r, int val) { dec(1, 0, n - 1, l, r, val); }
  void dec(int p, int l, int r, int a, int b, int v) {
    if (a > r || b < l)
      return;
    if (a <= l && r <= b) {
      seg[p].cdec(v);
      return;
    }
    int mid = (l + r) / 2;
    push(p);
    dec(2 * p, l, mid, a, b, v);
    dec(2 * p + 1, mid + 1, r, a, b, v);
    // pull(p);
  }

  T get(int p) { return seg[p + n]; }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],
               int finalHeight[]) {

  Seg<Node> w;
  w.init(1 << (int)ceil(log2(n)));
  for (int i = 0; i < n; i++) {
    w.upd(i, {0, 0});
  }
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      w.inc(left[i], right[i], height[i]);
    } else {
      w.dec(left[i], right[i], height[i]);
    }
    // cerr << w.get(3).inc << '\n';
  }

  for (int i = 1; i < w.n; i++) {
    w.push(i);
    // cerr << w.seg[0].inc << ';';
  }

  for (int i = 0; i < n; i++) {
    finalHeight[i] = w.get(i).inc;
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 124 ms 8064 KB Output is correct
3 Correct 141 ms 4076 KB Output is correct
4 Correct 373 ms 20176 KB Output is correct
5 Correct 226 ms 20660 KB Output is correct
6 Correct 197 ms 19156 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 5 ms 596 KB Output is correct
6 Correct 6 ms 672 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 130 ms 8108 KB Output is correct
9 Correct 135 ms 4100 KB Output is correct
10 Correct 395 ms 20176 KB Output is correct
11 Correct 203 ms 20684 KB Output is correct
12 Correct 196 ms 19052 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 133 ms 13984 KB Output is correct
15 Correct 33 ms 1980 KB Output is correct
16 Correct 661 ms 20192 KB Output is correct
17 Correct 241 ms 19628 KB Output is correct
18 Correct 207 ms 19624 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 212 KB Output is correct
4 Correct 6 ms 596 KB Output is correct
5 Correct 4 ms 596 KB Output is correct
6 Correct 4 ms 596 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 124 ms 8012 KB Output is correct
9 Correct 136 ms 4044 KB Output is correct
10 Correct 380 ms 20208 KB Output is correct
11 Correct 235 ms 20692 KB Output is correct
12 Correct 209 ms 19156 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 140 ms 13940 KB Output is correct
15 Correct 34 ms 1876 KB Output is correct
16 Correct 606 ms 20192 KB Output is correct
17 Correct 230 ms 19620 KB Output is correct
18 Correct 215 ms 19620 KB Output is correct
19 Correct 567 ms 59212 KB Output is correct
20 Correct 526 ms 59228 KB Output is correct
21 Correct 540 ms 59212 KB Output is correct
22 Correct 559 ms 59144 KB Output is correct
23 Correct 531 ms 59120 KB Output is correct
24 Correct 548 ms 59184 KB Output is correct
25 Correct 554 ms 59328 KB Output is correct
26 Correct 530 ms 59468 KB Output is correct
27 Correct 522 ms 59264 KB Output is correct
28 Correct 518 ms 59252 KB Output is correct
29 Correct 518 ms 59164 KB Output is correct
30 Correct 517 ms 59184 KB Output is correct