제출 #1009199

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1009199		SonicML	벽 (IOI14_wall)	C++14	100 / 100	701 ms	89088 KiB

wall

#include <iostream>
#include <vector>
#include "wall.h"

using namespace std;

int const INF = 1e5;

struct Node {
  int minn;
  int maxx;
};

Node combineNode(Node a, Node b) {
  Node c;
  c.minn = min(b.maxx, max(a.minn, b.minn));
  c.maxx = max(b.minn, min(a.maxx, b.maxx));
  return c;
}

struct SegmentTree {
  vector <Node> seg;

  SegmentTree(int n) {
    seg.resize(1 + 4 * n);
    for(int i = 1;i <= 4 * n;i++) {
      seg[i] = {0, INF};
    }
  }

  void cleanNode(int node, int from, int to) {
    if(from != to) {
      seg[node * 2] = combineNode(seg[node * 2], seg[node]);
      seg[node * 2 + 1] = combineNode(seg[node * 2 + 1], seg[node]);
      seg[node] = {0, INF};
    }
  }

  void update(int node, int from, int to, int x, int y, Node add) {
    if(from == x && to == y) {
      seg[node] = combineNode(seg[node], add);
      cleanNode(node, from, to);
    } else {
      int mid = (from + to) / 2;
      cleanNode(node * 2, from, mid);
      cleanNode(node * 2 + 1, mid+1, to);
      if(y <= mid) {
        update(node * 2, from, mid, x, y, add);
      } else if(mid < x) {
        update(node * 2 + 1, mid+1, to, x, y, add);
      } else {
        update(node * 2, from, mid, x, mid, add);
        update(node * 2 + 1, mid+1, to, mid+1, y, add);
      }
    }
  }

  Node query(int node, int from, int to, int x) {
    cleanNode(node, from, to);
    if(from == to) {
      return seg[node];
    } else {
      int mid = (from + to) / 2;
      if(x <= mid) {
        return query(node*2, from, mid, x);
      } else {
        return query(node*2+1, mid+1, to, x); 
      }
    }
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]) {
  SegmentTree seg(n);
  seg.update(1, 1, n, 1, n, {0, 0});
  for(int i = 0;i < k;i++) {
    int x = left[i]+1, y = right[i]+1;
    Node add;
    if(op[i] == 1) {
      add = {height[i], INF};
    } else {
      add = {0, height[i]};
    }
    seg.update(1, 1, n, x, y, add);
  }
  for(int i = 0;i < n;i++) {
    finalHeight[i] = seg.query(1, 1, n, i+1).minn;
  }
  return;
}
  

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