oj.uz

Submission #847850

# Submission time Handle Problem Language Result Execution time Memory
847850 2023-09-10T15:30:50 Z Derek0 Wall (IOI14_wall) C++17
100 / 100
 552 ms 108304 KB 
#include "wall.h"

#include <bits/stdc++.h>

using namespace std;

#define overload4(a, b, c, d, name, ...) name
#define rep1(i, n) for(ll i = 0; i < (n); ++i)
#define rep2(i, a, b) for(ll i = (a); i < (b); ++i)
#define rep3(i, a, b, c) for(ll i = (a); i < (b); i += (c))
#define rep(...) overload4(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define per1(i, n) for(ll i = (n) - 1; i >= 0; --i)
#define per2(i, a, b) for(ll i = (b) - 1; i >= a; --i)
#define per3(i, a, b, c) for(ll i = (b) - 1; i >= (a); i -= (c))
#define per(...) overload4(__VA_ARGS__, per3, per2, per1)(__VA_ARGS__)
#define pb emplace_back
#define lb(v,k) (ll) (lower_bound(all(v), (k)) - v.begin())
#define ub(v,k) (ll) (upper_bound(all(v), (k)) - v.begin())
#define all(a) a.begin(),a.end()
#define fi first
#define se second
#define PQ(T) priority_queue<T>
#define SPQ(T) priority_queue<T, vector<T>, greater<T>>
typedef long long ll;
typedef pair<ll,ll> P;
using vi = vector<ll>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vvvvi = vector<vvvi>;
using vp = vector<P>;
using vvp = vector<vp>;

constexpr int inf = (int) 1e9;

constexpr int _ = (int) 1e7;

ll mx[_], mn[_];
vi res;

void applyMax(int p, int h) {
  mx[p] = max<ll>(mx[p], h);
  mn[p] = max<ll>(mn[p], h);
}

void applyMin(int p, int h) {
  mx[p] = min<ll>(mx[p], h);
  mn[p] = min<ll>(mn[p], h);
}

void push(int p) {
  applyMin(2 * p, mn[p]);
  applyMin(2 * p + 1, mn[p]);
  applyMax(2 * p, mx[p]);
  applyMax(2 * p + 1, mx[p]);
  mx[p] = 0; mn[p] = inf;
}

void modify(int p, int l, int r, int ql, int qr, int h, int t) {
  if (r < ql || l > qr) return;
  if (ql <= l && r <= qr) {
    if (t == 1) applyMax(p, h);
    else applyMin(p, h);
    return;
  }
  int m = (l + r) / 2;
  push(p);
  modify(2 * p, l, m, ql, qr, h, t);
  modify(2 * p + 1, m + 1, r, ql, qr, h, t);
}

void traversal(int p, int l, int r) {
  if (l == r) {
    res.pb(mx[p]);
    return;
  }
  int m = (l + r) / 2;
  push(p);
  traversal(2 * p, l, m);
  traversal(2 * p + 1, m + 1, r);
}

void buildWall(int n, int k, int t[], int l[], int r[], int h[], int ans[]) {
  rep(i, k) modify(1, 0, n - 1, l[i], r[i], h[i], t[i]);
 
  traversal(1, 0, n - 1);
 
  rep(i, n) ans[i] = res[i];
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 4 ms 1116 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 108 ms 8168 KB Output is correct
3 Correct 129 ms 5048 KB Output is correct
4 Correct 347 ms 13764 KB Output is correct
5 Correct 218 ms 14180 KB Output is correct
6 Correct 217 ms 14280 KB Output is correct

Subtask #3
29.0 / 29.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 344 KB Output is correct
4 Correct 5 ms 1112 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 5 ms 1112 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 128 ms 8284 KB Output is correct
9 Correct 127 ms 5296 KB Output is correct
10 Correct 357 ms 13784 KB Output is correct
11 Correct 226 ms 14276 KB Output is correct
12 Correct 213 ms 14300 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 113 ms 8188 KB Output is correct
15 Correct 20 ms 2260 KB Output is correct
16 Correct 353 ms 14016 KB Output is correct
17 Correct 230 ms 13896 KB Output is correct
18 Correct 221 ms 14220 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 344 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 4 ms 1112 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1112 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 109 ms 8072 KB Output is correct
9 Correct 122 ms 5068 KB Output is correct
10 Correct 356 ms 13728 KB Output is correct
11 Correct 221 ms 14276 KB Output is correct
12 Correct 223 ms 14480 KB Output is correct
13 Correct 1 ms 344 KB Output is correct
14 Correct 111 ms 8272 KB Output is correct
15 Correct 20 ms 2252 KB Output is correct
16 Correct 365 ms 14052 KB Output is correct
17 Correct 222 ms 14020 KB Output is correct
18 Correct 216 ms 14020 KB Output is correct
19 Correct 527 ms 107848 KB Output is correct
20 Correct 519 ms 105656 KB Output is correct
21 Correct 538 ms 108180 KB Output is correct
22 Correct 521 ms 105128 KB Output is correct
23 Correct 518 ms 105120 KB Output is correct
24 Correct 522 ms 106020 KB Output is correct
25 Correct 527 ms 105232 KB Output is correct
26 Correct 529 ms 108304 KB Output is correct
27 Correct 552 ms 108092 KB Output is correct
28 Correct 518 ms 105128 KB Output is correct
29 Correct 518 ms 105128 KB Output is correct
30 Correct 528 ms 105132 KB Output is correct