oj.uz

Submission #1092461

# Submission time Handle Problem Language Result Execution time Memory
1092461 2024-09-24T07:11:50 Z May27_th Wall (IOI14_wall) C++17
100 / 100
 830 ms 151736 KB 
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,popcnt,lzcnt")
#include<bits/stdc++.h>
 
using namespace std;
 
#define i64 long long
#define mp make_pair
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int MAXN = 2e5 + 10;
const int INF = 1e9;
struct DataTree {
  const i64 INF = 1e18;
  struct Data {
    i64 mn = 0, mx = LLONG_MAX;
  };
  vector<Data> st;
  DataTree (int _N) : st(4 * _N + 4) {};
  void Apply(int id, i64 mn, i64 mx) {
    st[id].mn = max(st[id].mn, mn);
    st[id].mx = max(st[id].mx, st[id].mn);
    st[id].mx = min(st[id].mx, mx);
    st[id].mn = min(st[id].mn, st[id].mx);
  }
  void push(int id, int l, int r) {
    Apply(id * 2, st[id].mn, st[id].mx);
    Apply(id * 2 + 1, st[id].mn, st[id].mx);
    st[id].mn = 0; st[id].mx = LLONG_MAX;
  }
  void update(int id, int l, int r, int u, int v, i64 mn, i64 mx) {
    if (v < l || u > r) return;
    if (u <= l && r <= v) {
      Apply(id, mn, mx);
      return;
    }
    push(id, l, r);
    int mid = (l + r)/2;
    update(id * 2, l, mid, u, v, mn, mx);
    update(id * 2 + 1, mid + 1, r, u, v, mn, mx);
  }
  Data get(int id, int l, int r, int p) {
    if (l == r) return st[id];
    push(id, l, r);
    int mid = (l + r)/2;
    if (p <= mid) return get(id * 2, l, mid, p);
    return get(id * 2 + 1, mid + 1, r, p);
  }
};
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  DataTree T(n + 2);
  for (int i = 0; i < k; i ++) {
    if (op[i] == 1) T.update(1, 1, n, left[i] + 1, right[i] + 1, height[i], LLONG_MAX);
    else T.update(1, 1, n, left[i] + 1, right[i] + 1, 0, height[i]);
  }
  for (int i = 0; i < n; i ++) {
    finalHeight[i] = T.get(1, 1, n, i + 1).mn;
    // cout << finalHeight[i] << " ";
  }
}

Subtask #1
8.0 / 8.0

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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 94 ms 13888 KB Output is correct
3 Correct 116 ms 8584 KB Output is correct
4 Correct 335 ms 24400 KB Output is correct
5 Correct 249 ms 24952 KB Output is correct
6 Correct 198 ms 23304 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 1 ms 428 KB Output is correct
4 Correct 5 ms 1152 KB Output is correct
5 Correct 4 ms 1116 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 88 ms 13996 KB Output is correct
9 Correct 112 ms 8416 KB Output is correct
10 Correct 343 ms 24516 KB Output is correct
11 Correct 215 ms 24928 KB Output is correct
12 Correct 201 ms 23464 KB Output is correct
13 Correct 0 ms 344 KB Output is correct
14 Correct 92 ms 13908 KB Output is correct
15 Correct 19 ms 2396 KB Output is correct
16 Correct 337 ms 24480 KB Output is correct
17 Correct 214 ms 23724 KB Output is correct
18 Correct 206 ms 23888 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 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 5 ms 1116 KB Output is correct
5 Correct 4 ms 1220 KB Output is correct
6 Correct 4 ms 1116 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 90 ms 13968 KB Output is correct
9 Correct 112 ms 8620 KB Output is correct
10 Correct 352 ms 24404 KB Output is correct
11 Correct 215 ms 24916 KB Output is correct
12 Correct 204 ms 23376 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 90 ms 13904 KB Output is correct
15 Correct 20 ms 2396 KB Output is correct
16 Correct 331 ms 24276 KB Output is correct
17 Correct 222 ms 23780 KB Output is correct
18 Correct 216 ms 24144 KB Output is correct
19 Correct 830 ms 151632 KB Output is correct
20 Correct 791 ms 151556 KB Output is correct
21 Correct 791 ms 151636 KB Output is correct
22 Correct 787 ms 151632 KB Output is correct
23 Correct 792 ms 151636 KB Output is correct
24 Correct 756 ms 151636 KB Output is correct
25 Correct 756 ms 151632 KB Output is correct
26 Correct 757 ms 151736 KB Output is correct
27 Correct 754 ms 151636 KB Output is correct
28 Correct 758 ms 151636 KB Output is correct
29 Correct 768 ms 151584 KB Output is correct
30 Correct 772 ms 151628 KB Output is correct