oj.uz

Submission #798058

# Submission time Handle Problem Language Result Execution time Memory
798058 2023-07-30T10:30:52 Z erray Wall (IOI14_wall) C++17
100 / 100
 590 ms 89036 KB 
#include "wall.h"
//OMG PINK FLOYD REFERANCE

#include<bits/stdc++.h>

using namespace std;

#ifdef DEBUG 
  #include "/home/ioi/codes/ioi14_d1/debug.h"
#else 
  #define debug(...) void(37)
#endif

template<typename T> 
vector<T> inverse_fuck(T* a, int N) {
  vector<T> res(N);
  for (int i = 0; i < N; ++i) {
    res[i] = a[i];
  }
  return res;
}


const int inf = int(1e6);
struct node {
  int mx = 0, mn = inf;
  int set = -1;
  void push(node x) {
    if (x.set != -1) {
      set = x.set;
    } else if (set != -1) {
      set = max(set, x.mx);
      set = min(set, x.mn);
    } else {
      if (x.mx >= mn) {
        set = x.mx;
        assert(x.mn > mx);
      } else if (x.mn <= mx) {
        set = x.mn;
      } else {
        mx = max(mx, x.mx);
        mn = min(mn, x.mn);
      }
    }
  }
};
#define def int mid = (l + r) >> 1, rv = (v + (mid - l) * 2)
struct SegTree {
  vector<node> tree;
  int n;
  SegTree(int _n) : n(_n) {
    tree.resize(n * 2 - 1);
  }
  void push_tags(int v, int rv) {
    tree[v + 1].push(tree[v]);
    tree[rv].push(tree[v]);
    tree[v] = node{};
  }  
  void modify(int v, int l, int r, int ll, int rr, bool op, int x) {
    if (l >= ll && rr >= r) {
      node add{};
      (op ? add.mx : add.mn) = x;
      tree[v].push(add);
      return;
    }
    def;
    push_tags(v, rv);
    if (mid > ll) {
      modify(v + 1, l, mid, ll, rr, op, x);
    }
    if (mid < rr) {
      modify(rv, mid, r, ll, rr, op, x);
    } //check closed - open intervals just in-case
  }
  void push(int v, int l, int r, vector<int>& res) {
    debug(l, r, tree[v].mn, tree[v].mx);
    if (l + 1 == r) {
      res[l] = (tree[v].set == -1 ? tree[v].mx : tree[v].set);
      return;
    }
    def;
    push_tags(v, rv);
    push(v + 1, l, mid, res);
    push(rv, mid, r, res);
  }
  vector<int> get() {
    vector<int> res(n);
    push(0, 0, n, res);
    return res;
  }
  void modify(int l, int r, bool op, int x) {
    modify(0, 0, n, l, r + 1, op, x);
  }
};


void buildWall(int n, int k, int fuck_op[], int fuck_left[], int fuck_right[], int fuck_height[], int fuck_finalHeight[]){
  auto O = inverse_fuck(fuck_op, k);
  auto L = inverse_fuck(fuck_left, k);
  auto R = inverse_fuck(fuck_right, k);
  auto H = inverse_fuck(fuck_height, k);
  SegTree st(n);
  for (int i = 0; i < k; ++i) {
    debug(L[i], R[i], O[i] == 1, H[i]);
    st.modify(L[i], R[i], O[i] == 1, H[i]);
  }
  auto res = st.get();
  for (int i = 0; i < n; ++i) {
    fuck_finalHeight[i] = res[i];
  }
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 756 KB Output is correct
5 Correct 4 ms 852 KB Output is correct
6 Correct 4 ms 824 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 107 ms 15944 KB Output is correct
3 Correct 114 ms 7364 KB Output is correct
4 Correct 327 ms 28676 KB Output is correct
5 Correct 212 ms 29232 KB Output is correct
6 Correct 208 ms 27740 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 820 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 105 ms 21708 KB Output is correct
9 Correct 119 ms 11204 KB Output is correct
10 Correct 320 ms 28728 KB Output is correct
11 Correct 211 ms 29200 KB Output is correct
12 Correct 216 ms 27912 KB Output is correct
13 Correct 0 ms 300 KB Output is correct
14 Correct 107 ms 21784 KB Output is correct
15 Correct 19 ms 2260 KB Output is correct
16 Correct 321 ms 28788 KB Output is correct
17 Correct 210 ms 28128 KB Output is correct
18 Correct 226 ms 28024 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 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 4 ms 852 KB Output is correct
5 Correct 4 ms 828 KB Output is correct
6 Correct 4 ms 852 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 106 ms 21732 KB Output is correct
9 Correct 113 ms 11084 KB Output is correct
10 Correct 337 ms 28716 KB Output is correct
11 Correct 217 ms 29152 KB Output is correct
12 Correct 208 ms 27700 KB Output is correct
13 Correct 1 ms 300 KB Output is correct
14 Correct 107 ms 21868 KB Output is correct
15 Correct 19 ms 2272 KB Output is correct
16 Correct 316 ms 28732 KB Output is correct
17 Correct 217 ms 28140 KB Output is correct
18 Correct 209 ms 28068 KB Output is correct
19 Correct 501 ms 89012 KB Output is correct
20 Correct 507 ms 88980 KB Output is correct
21 Correct 499 ms 89020 KB Output is correct
22 Correct 493 ms 88988 KB Output is correct
23 Correct 494 ms 88984 KB Output is correct
24 Correct 496 ms 88984 KB Output is correct
25 Correct 498 ms 88972 KB Output is correct
26 Correct 517 ms 89036 KB Output is correct
27 Correct 537 ms 89004 KB Output is correct
28 Correct 498 ms 89008 KB Output is correct
29 Correct 590 ms 89008 KB Output is correct
30 Correct 512 ms 89036 KB Output is correct