Submission #1263567

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263567		minhtan1103	Wall (IOI14_wall)	C++20	100 / 100	1028 ms	151628 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxN = 2e6 + 5;
const int INF = 1e9 + 5;

struct Segtree{
  struct Node{
    int min_val;
    int max_val;
    Node(){
      min_val = 0;
      max_val = INF;
    }
    Node(int min_, int max_){
      min_val = min_;
      max_val = max_;
    }
    Node operator+(Node b){
      Node res;
      res.min_val = max(min_val, b.min_val);
      res.max_val = max(res.min_val, max_val);
      res.max_val = min(res.max_val, b.max_val);
      res.min_val = min(res.max_val, res.min_val);
      return res;
    }
  };
  Node st[4*maxN], lazy[4*maxN];

  void down(int id){
    Node val = lazy[id];

    st[id*2] = st[id*2] + val;
    lazy[id*2] = lazy[id*2] + val;

    st[id*2 + 1] = st[id*2 + 1] + val;
    lazy[id*2 + 1] = lazy[id*2 + 1] + val;
    lazy[id] = Node();
  }

  void update(int id, int l, int r, int u, int v, Node val){
    if (l > v || r < u)
      return;
    if (l >= u && r <= v){
      st[id] = st[id] + val;
      lazy[id] = lazy[id] + val;
      return;
    }
    down(id);
    int mid = (l + r)/2;
    update(id*2, l, mid, u, v, val);
    update(id*2 + 1, mid+1, r, u, v, val);
    st[id] = st[id*2] + st[id*2 + 1];
  }

  void update(int n, int l, int r, Node val){
    update(1, 1, n, l, r, val);
  }

  Node get(int id, int l, int r, int u, int v){
    if (l > v || r < u)
      return Node();
    if (l >= u && r <= v)
      return st[id];
    down(id);
    int mid = (l + r)/2;
    return get(id*2, l, mid, u, v) +
            get(id*2 + 1, mid+1, r, u, v);
  }

  int get(int n, int l, int r){
    return get(1, 1, n, l, r).min_val;
  }
} seg;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i = 0; i < k; ++i){
    if (op[i] == 1){
      seg.update(n, left[i] + 1, right[i] + 1, Segtree::Node(height[i], INF));
    }
    else{
      seg.update(n, left[i] + 1, right[i] + 1, Segtree::Node(0, height[i]));
    }
  }
  for (int i = 0; i < n; ++i){
    finalHeight[i] = seg.get(n, i+1, i+1);
  }


  return;
}

• Subtask 1: 8 / 8
• Subtask 2: 24 / 24
• Subtask 3: 29 / 29
• Subtask 4: 39 / 39