oj.uz

Submission #1075238

# Submission time Handle Problem Language Result Execution time Memory
1075238 2024-08-25T21:21:45 Z Boas Wall (IOI14_wall) C++17
100 / 100
 2029 ms 102400 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef vector<vi> vvi;

struct val
{
  int minv = 0, maxv = 100'000;
  val operator+(const val &b)
  {
    val a = *this, res;
    res.minv = max(a.minv, b.minv);
    res.maxv = min(a.maxv, b.maxv);
    if (b.minv > maxv)
      res.maxv = b.minv;
    if (b.maxv < minv)
      res.minv = b.maxv;
    return res;
  }
  val &operator+=(const val &b)
  {
    minv = max(minv, b.minv);
    maxv = min(maxv, b.maxv);
    if (b.minv > maxv)
      maxv = b.minv;
    if (b.maxv < minv)
      minv = b.maxv;
    return *this;
  }
};

vector<val> tree, lazy;
int treeN = 1;

void pull(int i)
{
  tree[i] = tree[2 * i] + tree[2 * i + 1];
}

void push(int i)
{
  tree[i] += lazy[i];
  if (i < treeN)
  {
    lazy[2 * i] += lazy[i];
    lazy[2 * i + 1] += lazy[i];
  }
  lazy[i] = {};
}

val query(int i, int l, int r, int ql, int qr, int v, int op)
{
  push(i);
  if (qr < l || r < ql)
    return {};
  if (ql <= l && r <= qr)
  {
    if (op == 1)
    {
      val add = {v, 100'000};
      lazy[i] += add;
      push(i);
    }
    else if (op == 2)
    {
      val add = {0, v};
      lazy[i] += add;
      push(i);
    }
    return tree[i];
  }
  int m = (l + r) / 2;
  val res = query(2 * i, l, m, ql, qr, v, op) +
            query(2 * i + 1, m + 1, r, ql, qr, v, op);
  pull(i);
  return res;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
  while (treeN < n)
    treeN *= 2;
  tree = lazy = vector<val>(treeN * 2);
  for (int i = 0; i < k; i++)
  {
    int l = left[i], r = right[i], h = height[i];
    query(1, 0, treeN - 1, l, r, h, op[i]);
  }
  for (int i = 0; i < n; i++)
  {
    finalHeight[i] = query(1, 0, treeN - 1, i, i, 0, 0).minv;
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 13 ms 1168 KB Output is correct
5 Correct 9 ms 1116 KB Output is correct
6 Correct 10 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 93 ms 13908 KB Output is correct
3 Correct 206 ms 8496 KB Output is correct
4 Correct 659 ms 22608 KB Output is correct
5 Correct 379 ms 23636 KB Output is correct
6 Correct 425 ms 21844 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 10 ms 1116 KB Output is correct
5 Correct 9 ms 1112 KB Output is correct
6 Correct 12 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 89 ms 13908 KB Output is correct
9 Correct 209 ms 8536 KB Output is correct
10 Correct 663 ms 22352 KB Output is correct
11 Correct 372 ms 23636 KB Output is correct
12 Correct 368 ms 21816 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 91 ms 13940 KB Output is correct
15 Correct 40 ms 2644 KB Output is correct
16 Correct 654 ms 22608 KB Output is correct
17 Correct 392 ms 22060 KB Output is correct
18 Correct 429 ms 22152 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 348 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 9 ms 1112 KB Output is correct
5 Correct 9 ms 1116 KB Output is correct
6 Correct 10 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 90 ms 13908 KB Output is correct
9 Correct 220 ms 8416 KB Output is correct
10 Correct 620 ms 22608 KB Output is correct
11 Correct 369 ms 23520 KB Output is correct
12 Correct 380 ms 21844 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 87 ms 13936 KB Output is correct
15 Correct 39 ms 2652 KB Output is correct
16 Correct 650 ms 23000 KB Output is correct
17 Correct 380 ms 22028 KB Output is correct
18 Correct 391 ms 22096 KB Output is correct
19 Correct 1922 ms 102400 KB Output is correct
20 Correct 1937 ms 100008 KB Output is correct
21 Correct 1887 ms 102308 KB Output is correct
22 Correct 1915 ms 99868 KB Output is correct
23 Correct 1872 ms 99924 KB Output is correct
24 Correct 1977 ms 99980 KB Output is correct
25 Correct 2029 ms 99936 KB Output is correct
26 Correct 1945 ms 102312 KB Output is correct
27 Correct 1923 ms 102360 KB Output is correct
28 Correct 1920 ms 99956 KB Output is correct
29 Correct 1904 ms 100004 KB Output is correct
30 Correct 1977 ms 99920 KB Output is correct