oj.uz

Submission #847848

# Submission time Handle Problem Language Result Execution time Memory
847848 2023-09-10T15:12:46 Z Derek0 Wall (IOI14_wall) C++17
100 / 100
 571 ms 107944 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) {
  applyMax(2 * p, mx[p]);
  applyMax(2 * p + 1, mx[p]);
  applyMin(2 * p, mn[p]);
  applyMin(2 * p + 1, mn[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 0 ms 348 KB Output is correct
2 Correct 2 ms 360 KB Output is correct
3 Correct 1 ms 500 KB Output is correct
4 Correct 6 ms 1116 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 5 ms 1116 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 496 KB Output is correct
2 Correct 117 ms 8056 KB Output is correct
3 Correct 122 ms 5072 KB Output is correct
4 Correct 371 ms 13780 KB Output is correct
5 Correct 218 ms 14276 KB Output is correct
6 Correct 221 ms 14296 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 2 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 6 ms 1112 KB Output is correct
5 Correct 4 ms 1112 KB Output is correct
6 Correct 4 ms 1368 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 109 ms 8272 KB Output is correct
9 Correct 122 ms 5068 KB Output is correct
10 Correct 337 ms 13768 KB Output is correct
11 Correct 222 ms 14276 KB Output is correct
12 Correct 213 ms 14276 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 111 ms 8248 KB Output is correct
15 Correct 21 ms 2252 KB Output is correct
16 Correct 345 ms 14044 KB Output is correct
17 Correct 226 ms 14276 KB Output is correct
18 Correct 216 ms 13988 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct
3 Correct 1 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 1124 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 106 ms 8272 KB Output is correct
9 Correct 123 ms 5040 KB Output is correct
10 Correct 348 ms 13784 KB Output is correct
11 Correct 228 ms 14192 KB Output is correct
12 Correct 263 ms 14136 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 122 ms 8092 KB Output is correct
15 Correct 22 ms 2312 KB Output is correct
16 Correct 356 ms 14052 KB Output is correct
17 Correct 219 ms 14024 KB Output is correct
18 Correct 215 ms 14020 KB Output is correct
19 Correct 562 ms 107800 KB Output is correct
20 Correct 517 ms 105264 KB Output is correct
21 Correct 571 ms 107712 KB Output is correct
22 Correct 538 ms 105668 KB Output is correct
23 Correct 523 ms 105932 KB Output is correct
24 Correct 524 ms 105736 KB Output is correct
25 Correct 525 ms 105288 KB Output is correct
26 Correct 523 ms 107944 KB Output is correct
27 Correct 566 ms 107832 KB Output is correct
28 Correct 528 ms 105896 KB Output is correct
29 Correct 533 ms 105984 KB Output is correct
30 Correct 520 ms 105772 KB Output is correct