oj.uz

Submission #257637

# Submission time Handle Problem Language Result Execution time Memory
257637 2020-08-04T13:50:07 Z Haunted_Cpp Wall (IOI14_wall) C++17
100 / 100
 1124 ms 167644 KB 
/**
 * author: Haunted_Cpp
**/
 
#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

#pragma GCC target("fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
 
template<typename T> ostream &operator << (ostream &os, const vector<T> &v) { os << '{'; string sep; for (const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename T, size_t size> ostream &operator << (ostream &os, const array<T, size> &arr) { os << '{'; string sep; for (const auto &x : arr) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream &operator << (ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void debug_out() { cerr << endl; }
template<typename Head, typename... Tail> void debug_out(Head H, Tail... T) { cerr << ' ' << H; debug_out(T...); }
 
#ifdef LOCAL
#define debug(...) cerr << "(" << #__VA_ARGS__ << "):", debug_out(__VA_ARGS__)
#else
#define debug(...) 47
#endif

const int UP = 1e9;

class SegmentTree {
private:
  struct Node {
    int mn;
    int mx;
    int aumentar;
    int diminuir;
    Node () {
      mn = mx = 0;
      aumentar = -1;
      diminuir = UP;
    }
    void merge(Node l, Node r) {
      mn = min(l.mn, r.mn);
      mx = max(l.mx, r.mx);
    }
  };
  const int LO, HI;
  vector<Node> seg;
  vector<int> ans;
  void push_aumentar(int l, int r, int node) {
    if (seg[node].aumentar == -1) return;
    seg[node].mn = max(seg[node].mn, seg[node].aumentar);
    seg[node].mx = max(seg[node].mx, seg[node].mn);
    if (l != r) {
      seg[2 * node + 1].aumentar = max(seg[2 * node + 1].aumentar, seg[node].aumentar);
      seg[2 * node + 2].aumentar = max(seg[2 * node + 2].aumentar, seg[node].aumentar);
      if (seg[2 * node + 1].aumentar >= seg[2 * node + 1].diminuir) {
        seg[2 * node + 1].diminuir = seg[2 * node + 1].aumentar;
      }
      if (seg[2 * node + 2].aumentar >= seg[2 * node + 2].diminuir) {
        seg[2 * node + 2].diminuir = seg[2 * node + 2].aumentar;
      }
    }
    seg[node].aumentar = -1;
  }
  void push_diminuir(int l, int r, int node) {
    if (seg[node].diminuir == UP) return;
    seg[node].mx = min(seg[node].mx, seg[node].diminuir);
    seg[node].mn = min(seg[node].mn, seg[node].mx);
    if (l != r) {
      seg[2 * node + 1].diminuir = min(seg[2 * node + 1].diminuir, seg[node].diminuir);
      seg[2 * node + 2].diminuir = min(seg[2 * node + 2].diminuir, seg[node].diminuir);
      if (seg[2 * node + 1].diminuir <= seg[2 * node + 1].aumentar) {
        seg[2 * node + 1].aumentar = seg[2 * node + 1].diminuir;
      }
      if (seg[2 * node + 2].diminuir <= seg[2 * node + 2].aumentar) {
        seg[2 * node + 2].aumentar = seg[2 * node + 2].diminuir;
      }
    }
    seg[node].diminuir = UP;
  }
  void pushdown(int l, int r, int node) {
    push_aumentar(l, r, node);
    push_diminuir(l, r, node);
  }
  void range_update(int ql, int qr, int delta, int l, int r, int node, bool task) {
    pushdown(l, r, node);
    if (l > qr || r < ql) return;
    if (l >= ql && r <= qr) {
      if(task) seg[node].aumentar = delta;
      else seg[node].diminuir = delta;
      pushdown(l, r, node);
      return;
    }
    const int mid = l + (r - l) / 2;
    range_update(ql, qr, delta, l, mid, 2 * node + 1, task);
    range_update(ql, qr, delta, mid + 1, r, 2 * node + 2, task);
    seg[node].merge(seg[2 * node + 1], seg[2 * node + 2]);
  }
  void print(int l, int r, int node) {
    pushdown(l, r, node);
    if (l == r) {
      ans.emplace_back(seg[node].mn);
      return;
    }
    const int mid = l + (r - l) / 2;
    print(l, mid, 2 * node + 1);
    print(mid + 1, r, 2 * node + 2);
  }
public:
  SegmentTree(int n) : LO(0), HI(n - 1) {
    seg.resize(4 * n);
  }
  void range_update(int ql, int qr, int delta, bool task) {
    range_update(ql, qr, delta, LO, HI, 0, task);
  }
  vector<int> print_ans() {
    print(LO, HI, 0);
    return ans;
  }
};

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  SegmentTree seg(n);
  for (int i = 0; i < k; i++) {
    int task = op[i];
    int lo = left[i];
    int hi = right[i];
    int delta = height[i];
    if (task == 1) {
      seg.range_update(lo, hi, delta, true);
    } else {
      seg.range_update(lo, hi, delta, false);
    } 
  }
  vector<int> ans = seg.print_ans();
  for (int i = 0; i < n; i++) finalHeight[i] = ans[i];
  return;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 10 ms 1280 KB Output is correct
5 Correct 7 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 183 ms 14032 KB Output is correct
3 Correct 273 ms 8952 KB Output is correct
4 Correct 761 ms 25460 KB Output is correct
5 Correct 388 ms 25844 KB Output is correct
6 Correct 371 ms 24308 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 12 ms 1280 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 182 ms 14072 KB Output is correct
9 Correct 254 ms 8824 KB Output is correct
10 Correct 727 ms 25332 KB Output is correct
11 Correct 392 ms 26032 KB Output is correct
12 Correct 376 ms 24436 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 184 ms 13968 KB Output is correct
15 Correct 56 ms 2680 KB Output is correct
16 Correct 1124 ms 25336 KB Output is correct
17 Correct 386 ms 24820 KB Output is correct
18 Correct 375 ms 24820 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 11 ms 1240 KB Output is correct
5 Correct 6 ms 1280 KB Output is correct
6 Correct 6 ms 1280 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 181 ms 13944 KB Output is correct
9 Correct 250 ms 8760 KB Output is correct
10 Correct 721 ms 25332 KB Output is correct
11 Correct 391 ms 25844 KB Output is correct
12 Correct 375 ms 24308 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 182 ms 13944 KB Output is correct
15 Correct 55 ms 2680 KB Output is correct
16 Correct 1067 ms 25460 KB Output is correct
17 Correct 370 ms 24948 KB Output is correct
18 Correct 380 ms 24924 KB Output is correct
19 Correct 959 ms 167644 KB Output is correct
20 Correct 977 ms 167520 KB Output is correct
21 Correct 1004 ms 167456 KB Output is correct
22 Correct 939 ms 167520 KB Output is correct
23 Correct 926 ms 167536 KB Output is correct
24 Correct 936 ms 167512 KB Output is correct
25 Correct 930 ms 167512 KB Output is correct
26 Correct 996 ms 167520 KB Output is correct
27 Correct 934 ms 167440 KB Output is correct
28 Correct 915 ms 167504 KB Output is correct
29 Correct 979 ms 167432 KB Output is correct
30 Correct 971 ms 167504 KB Output is correct