oj.uz

Submission #540333

# Submission time Handle Problem Language Result Execution time Memory
540333 2022-03-20T03:22:44 Z schiftyfive4 Wall (IOI14_wall) C++14
100 / 100
 1405 ms 149208 KB 
#include <bits/stdc++.h>
#include "wall.h"
using namespace std;

const int inf = 2e9;

template<class T>
struct SegTree {
  int n;
  vector<T> t, tag;    
  SegTree(int _) {
    n = _;
    t.resize(4 * n, {0, 0});
    tag.resize(4 * n, {0, inf});
  }
  void apply(T &x, T &val) {
    if (x.first <= val.first && val.second <= x.second) {
      x = val;
    } else if (x.second <= val.first) {
      x.first = val.first;
      x.second = val.first;
    } else if (x.first >= val.second) {
      x.first = val.second;
      x.second = val.second;
    } else if (x.first <= val.first && val.first <= x.second && x.second <= val.second) {
      x.first = val.first;
    } else if (val.first <= x.first && x.first <= val.second && val.second <= x.second) {
      x.second = val.second;
    }
  }
  T join(T &y, T &z) {
    T res;
    res.first = min(y.first, z.first);
    res.second = max(y.second, z.second);
    return res;
  }
  void push(int v) {
    apply(t[2 * v], tag[v]);
    apply(tag[2 * v], tag[v]);
    apply(t[2 * v + 1], tag[v]);
    apply(tag[2 * v + 1], tag[v]);
    tag[v] = {0, inf};
  }
  void modify(int v, int l, int r, int a, int b, T val) {
    if (l > b || r < a) {
      return;
    }
    if (a <= l && r <= b) {
      // cout << "(l, r) = " << l << ' ' << r << '\n';
      // cout << "val: " << val.first << ' ' << val.second << '\n';
      // cout << "before: " << t[v].first << ' ' << t[v].second << '\n';
      apply(t[v], val);
      apply(tag[v], val);
      // cout << "after: " << t[v].first << ' ' << t[v].second << '\n';
      // cout << tag[v].first << ' ' << tag[v].second << '\n';
      // cout << '\n';
      return;
    }
    push(v);
    int m = (l + r) / 2;
    modify(2 * v, l, m, a, b, val);
    modify(2 * v + 1, m + 1, r, a, b, val);
    t[v] = join(t[2 * v], t[2 * v + 1]);
  }
  int query(int v, int l, int r, int pos) {
    // cout << l << ' ' << r << ' ' << t[v].first << ' ' << t[v].second << '\n';
    if (l == r) {
      assert(t[v].first == t[v].second);
      return t[v].first;
    }
    push(v);
    int m = (l + r) / 2;
    if (pos <= m) {
      return query(2 * v, l, m, pos);
    }
    return query(2 * v + 1, m + 1, r, pos);
  }
  void modify(int a, int b, T val) {
    modify(1, 0, n - 1, a, b, val);
  }
  int query(int pos) {
    return query(1, 0, n - 1, pos);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  // cout << '\n';
  SegTree<pair<int, int>> t(n);
  for (int i = 0; i < k; i++) {
    if (op[i] == 1) {
      t.modify(left[i], right[i], {height[i], inf});
    } else {
      t.modify(left[i], right[i], {0, height[i]});
    }
  }
  // cout << "\nbruh\n";
  // for (int j = 0; j < n; j++) {
  //   cout << t.query(j) << ' ';
  // }
  // cout << '\n';
  for (int i = 0; i < n; i++) {
    finalHeight[i] = t.query(i);
  }
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 9 ms 1136 KB Output is correct
5 Correct 7 ms 1108 KB Output is correct
6 Correct 8 ms 1108 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 134 ms 8100 KB Output is correct
3 Correct 232 ms 4820 KB Output is correct
4 Correct 660 ms 22752 KB Output is correct
5 Correct 354 ms 22088 KB Output is correct
6 Correct 356 ms 23468 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 316 KB Output is correct
4 Correct 9 ms 1108 KB Output is correct
5 Correct 10 ms 1076 KB Output is correct
6 Correct 7 ms 1108 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 146 ms 13868 KB Output is correct
9 Correct 227 ms 8540 KB Output is correct
10 Correct 684 ms 22860 KB Output is correct
11 Correct 356 ms 22180 KB Output is correct
12 Correct 345 ms 23384 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 137 ms 14028 KB Output is correct
15 Correct 44 ms 2412 KB Output is correct
16 Correct 773 ms 22628 KB Output is correct
17 Correct 394 ms 23288 KB Output is correct
18 Correct 408 ms 23212 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 3 ms 340 KB Output is correct
4 Correct 10 ms 1076 KB Output is correct
5 Correct 7 ms 1108 KB Output is correct
6 Correct 8 ms 1148 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 136 ms 13900 KB Output is correct
9 Correct 230 ms 8648 KB Output is correct
10 Correct 670 ms 22748 KB Output is correct
11 Correct 359 ms 21964 KB Output is correct
12 Correct 349 ms 23244 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 133 ms 13924 KB Output is correct
15 Correct 44 ms 2440 KB Output is correct
16 Correct 770 ms 22780 KB Output is correct
17 Correct 398 ms 23340 KB Output is correct
18 Correct 401 ms 23228 KB Output is correct
19 Correct 1405 ms 148632 KB Output is correct
20 Correct 1331 ms 148800 KB Output is correct
21 Correct 1385 ms 148932 KB Output is correct
22 Correct 1339 ms 148608 KB Output is correct
23 Correct 1317 ms 148788 KB Output is correct
24 Correct 1330 ms 148952 KB Output is correct
25 Correct 1357 ms 148780 KB Output is correct
26 Correct 1378 ms 148904 KB Output is correct
27 Correct 1404 ms 148844 KB Output is correct
28 Correct 1332 ms 149208 KB Output is correct
29 Correct 1337 ms 148952 KB Output is correct
30 Correct 1348 ms 149028 KB Output is correct