oj.uz

Submission #671056

# Submission time Handle Problem Language Result Execution time Memory
671056 2022-12-11T18:20:07 Z ThinGarfield Wall (IOI14_wall) C++11
100 / 100
 802 ms 84032 KB 
#include "wall.h"

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

#define F first
#define S second
#define lc 2 * p
#define rc 2 * p + 1

constexpr int logn = 21;
constexpr int maxn = (1 << logn);
constexpr ll infty = LLONG_MAX;

pll seg[maxn * 2];

// t1 is old trim; t2 is new trim
pll combine(pll t1, pll t2) {
  if (t1.F > t2.S) return make_pair(t2.S, t2.S);
  if (t2.F > t1.S) return make_pair(t2.F, t2.F);
  return make_pair(max(t1.F, t2.F), min(t1.S, t2.S));
}

void pushdn(int p) {
  seg[lc] = combine(seg[lc], seg[p]);
  seg[rc] = combine(seg[rc], seg[p]);
  seg[p] = make_pair(0, infty);  // makes p irrelevant
}

void rangeupdate(int p, int l, int r, int a, int b, pll val) {
  if (a > r || b < l) return;
  if (a <= l && r <= b) {
    seg[p] = combine(seg[p], val);
    return;
  }
  pushdn(p);
  int mid = (l + r) / 2;
  rangeupdate(lc, l, mid, a, b, val);
  rangeupdate(rc, mid + 1, r, a, b, val);
}

pll walkseg(int p, int l, int r, int idx) {
  if (l == r) {
    assert(idx == l);
    return seg[p];
  }
  int mid = (l + r) / 2;
  if (idx <= mid) {
    return combine(walkseg(lc, l, mid, idx), seg[p]);
  } else {
    return combine(walkseg(rc, mid + 1, r, idx), seg[p]);
  }
}

ll compute(pll trim, ll val) {
  if (val < trim.F) return trim.F;
  if (val < trim.S) return trim.S;
  return val;
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  // cout << n << ' ' << k << '\n';
  for (int i = 0; i < k; i++) {
    // cout << "query " << op[i] << ' ' << left[i] << ' ' << right[i] << ' ' << height[i] << '\n';
    if (op[i] == 1) {
      rangeupdate(1, 0, maxn - 1, left[i], right[i], make_pair(height[i], infty));
    } else {
      rangeupdate(1, 0, maxn - 1, left[i], right[i], make_pair(0, height[i]));
    }
  }
  for (int i = 0; i < n; i++) {
    finalHeight[i] = compute(walkseg(1, 0, maxn - 1, i), 0);
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 6 ms 940 KB Output is correct
6 Correct 6 ms 852 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 238 ms 14124 KB Output is correct
3 Correct 160 ms 8052 KB Output is correct
4 Correct 425 ms 21520 KB Output is correct
5 Correct 304 ms 22524 KB Output is correct
6 Correct 289 ms 21136 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 444 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 7 ms 828 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 232 ms 14024 KB Output is correct
9 Correct 161 ms 8044 KB Output is correct
10 Correct 457 ms 21468 KB Output is correct
11 Correct 315 ms 22524 KB Output is correct
12 Correct 299 ms 20960 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 251 ms 14028 KB Output is correct
15 Correct 33 ms 1988 KB Output is correct
16 Correct 561 ms 21804 KB Output is correct
17 Correct 305 ms 21144 KB Output is correct
18 Correct 303 ms 21144 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 3 ms 520 KB Output is correct
3 Correct 3 ms 448 KB Output is correct
4 Correct 9 ms 872 KB Output is correct
5 Correct 6 ms 852 KB Output is correct
6 Correct 6 ms 852 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 257 ms 14048 KB Output is correct
9 Correct 163 ms 8044 KB Output is correct
10 Correct 472 ms 21488 KB Output is correct
11 Correct 302 ms 22536 KB Output is correct
12 Correct 286 ms 20936 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 237 ms 13984 KB Output is correct
15 Correct 33 ms 2100 KB Output is correct
16 Correct 551 ms 21744 KB Output is correct
17 Correct 289 ms 21208 KB Output is correct
18 Correct 298 ms 21152 KB Output is correct
19 Correct 792 ms 83792 KB Output is correct
20 Correct 770 ms 81228 KB Output is correct
21 Correct 779 ms 84032 KB Output is correct
22 Correct 765 ms 81180 KB Output is correct
23 Correct 777 ms 81372 KB Output is correct
24 Correct 789 ms 81396 KB Output is correct
25 Correct 774 ms 81228 KB Output is correct
26 Correct 802 ms 83804 KB Output is correct
27 Correct 786 ms 83744 KB Output is correct
28 Correct 770 ms 81100 KB Output is correct
29 Correct 774 ms 81400 KB Output is correct
30 Correct 777 ms 81196 KB Output is correct