oj.uz

Submission #847765

# Submission time Handle Problem Language Result Execution time Memory
847765 2023-09-10T10:55:07 Z Derek0 Wall (IOI14_wall) C++17
100 / 100
 528 ms 200884 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 ll inf = (ll) 1e9;

constexpr int _ = (int) 1e7;

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

void apply(ll p, ll h) {
  mx[p] = mn[p] = tag[p] = h;
}

void push(ll p) {
  if (tag[p] != -1) {
    apply(2 * p, tag[p]);
    apply(2 * p + 1, tag[p]);
    tag[p] = -1;
  }
}

void pull(ll p) {
  mx[p] = max(mx[2 * p], mx[2 * p + 1]);
  mn[p] = min(mn[2 * p], mn[2 * p + 1]);
}

void Add(ll p, ll l, ll r, ll ql, ll qr, ll h) {
  if (r < ql || l > qr) return;
  if (ql <= l && r <= qr) {
    if (mx[p] <= h) { apply(p, h); return; }
    if (mn[p] >= h) return;
    if (l == r) return;
  }
  ll m = (l + r) / 2;
  push(p);
  Add(2 * p, l, m, ql, qr, h);
  Add(2 * p + 1, m + 1, r, ql, qr, h);
  pull(p);
}

void Remove(ll p, ll l, ll r, ll ql, ll qr, ll h) {
  if (r < ql || l > qr) return;
  if (ql <= l && r <= qr) {
    if (mn[p] >= h) { apply(p, h); return; }
    if (mx[p] <= h) return;
    if (l == r) return;
  }
  ll m = (l + r) / 2;
  push(p);
  Remove(2 * p, l, m, ql, qr, h);
  Remove(2 * p + 1, m + 1, r, ql, qr, h);
  pull(p);
}

void traversal(ll p, ll l, ll r) {
  if (l == r) {
    res.pb(mn[p]);
    return;
  }
  ll 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(p, _) tag[p] = -1;

  rep(i, k) {
    if (t[i] == 1) Add(1, 0, n - 1, l[i], r[i], h[i]);
    else Remove(1, 0, n - 1, l[i], r[i], h[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 13 ms 80472 KB Output is correct
2 Correct 10 ms 80728 KB Output is correct
3 Correct 10 ms 80728 KB Output is correct
4 Correct 14 ms 81244 KB Output is correct
5 Correct 12 ms 81240 KB Output is correct
6 Correct 13 ms 81240 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 80472 KB Output is correct
2 Correct 122 ms 94212 KB Output is correct
3 Correct 128 ms 88636 KB Output is correct
4 Correct 344 ms 105412 KB Output is correct
5 Correct 231 ms 104620 KB Output is correct
6 Correct 231 ms 103108 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 80472 KB Output is correct
2 Correct 11 ms 80728 KB Output is correct
3 Correct 10 ms 80728 KB Output is correct
4 Correct 14 ms 81240 KB Output is correct
5 Correct 14 ms 81240 KB Output is correct
6 Correct 13 ms 81240 KB Output is correct
7 Correct 9 ms 80476 KB Output is correct
8 Correct 125 ms 94424 KB Output is correct
9 Correct 128 ms 88528 KB Output is correct
10 Correct 350 ms 105208 KB Output is correct
11 Correct 229 ms 104644 KB Output is correct
12 Correct 230 ms 103008 KB Output is correct
13 Correct 9 ms 80472 KB Output is correct
14 Correct 123 ms 94264 KB Output is correct
15 Correct 34 ms 82548 KB Output is correct
16 Correct 436 ms 103876 KB Output is correct
17 Correct 228 ms 104900 KB Output is correct
18 Correct 227 ms 103204 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 80472 KB Output is correct
2 Correct 10 ms 80732 KB Output is correct
3 Correct 10 ms 80732 KB Output is correct
4 Correct 14 ms 81244 KB Output is correct
5 Correct 12 ms 81240 KB Output is correct
6 Correct 13 ms 81496 KB Output is correct
7 Correct 9 ms 80476 KB Output is correct
8 Correct 118 ms 94288 KB Output is correct
9 Correct 130 ms 88524 KB Output is correct
10 Correct 338 ms 105208 KB Output is correct
11 Correct 229 ms 104660 KB Output is correct
12 Correct 223 ms 103088 KB Output is correct
13 Correct 9 ms 80472 KB Output is correct
14 Correct 125 ms 94136 KB Output is correct
15 Correct 33 ms 82512 KB Output is correct
16 Correct 425 ms 103848 KB Output is correct
17 Correct 236 ms 105012 KB Output is correct
18 Correct 228 ms 103120 KB Output is correct
19 Correct 528 ms 198312 KB Output is correct
20 Correct 511 ms 196380 KB Output is correct
21 Correct 511 ms 200428 KB Output is correct
22 Correct 506 ms 197544 KB Output is correct
23 Correct 514 ms 197700 KB Output is correct
24 Correct 513 ms 198104 KB Output is correct
25 Correct 519 ms 196776 KB Output is correct
26 Correct 519 ms 200884 KB Output is correct
27 Correct 509 ms 200616 KB Output is correct
28 Correct 511 ms 197620 KB Output is correct
29 Correct 508 ms 196344 KB Output is correct
30 Correct 507 ms 196180 KB Output is correct