### Idea

OIer 和 ACMer 的思维果然有很大的区别。。。

public class Solution {
public List getSkyline(int[][] buildings) {
List results = new ArrayList<>();
PriorityQueue rightHeap = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer i1, Integer i2) {
return Integer.compare(buildings[i1][1], buildings[i2][1]);
}
});
PriorityQueue heightHeap = new PriorityQueue<>(new Comparator() {
@Override
public int compare(Integer i1, Integer i2) {
return Integer.compare(buildings[i2][2], buildings[i1][2]);
}
});
int prev = 0;
for(int i = 0; i < buildings.length; i++) {
while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] < buildings[i][0]) {
int b = rightHeap.poll();
heightHeap.remove(b);
while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] == buildings[b][1]) {
b = rightHeap.poll();
heightHeap.remove(b);
}
int height = heightHeap.isEmpty() ? 0 : buildings[heightHeap.peek()][2];
if (height != prev) {
int[] result = new int[2];
result[0] = buildings[b][1];
result[1] = height;
prev = height;
}
}
while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] == buildings[i][0]) {
int b = rightHeap.poll();
heightHeap.remove(b);
}
rightHeap.offer(i);
heightHeap.offer(i);
while (i < buildings.length - 1 && buildings[i][0] == buildings[i + 1][0]) {
i++;
rightHeap.offer(i);
heightHeap.offer(i);
}
int height = buildings[heightHeap.peek()][2];
if (height != prev) {
int[] result = new int[2];
result[0] = buildings[i][0];
result[1] = height;
prev = height;
}
}

while (!rightHeap.isEmpty()) {
int b = rightHeap.poll();
heightHeap.remove(b);
while (!rightHeap.isEmpty() && buildings[rightHeap.peek()][1] == buildings[b][1]) {
b = rightHeap.poll();
heightHeap.remove(b);
}
int height = heightHeap.isEmpty() ? 0 : buildings[heightHeap.peek()][2];
if (height != prev) {
int[] result = new int[2];
result[0] = buildings[b][1];
result[1] = height;
prev = height;
}
}
return results;
}



### Code

#include
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
#define maxn 10010
using namespace std;
int tree[maxn*4],lazy[maxn*4],wide,tem,ans[maxn];
void chma(int &x,int y){x=max(x,y);}
void pushdown(int p){
int t=lazy[p];lazy[p]=0;
chma(tree[ls],t),chma(tree[rs],t);
chma(lazy[ls],t),chma(lazy[rs],t);
}
void insert(int l,int r,int L,int R,int k,int p){
if (l>R||r=L&&r<=R){
chma(lazy[p],k),chma(tree[p],k);
return;
}
if (lazy[p]) pushdown(p);
insert(l,mid,L,R,k,ls),insert(mid+1,r,L,R,k,rs);
}
void query(int l,int r,int p){
if (l==r){
ans[l]=tree[p];
return;
}
if (lazy[p]) pushdown(p);
query(l,mid,ls),query(mid+1,r,rs);
}
int main(){
ios::sync_with_stdio(false);
int x,y,z;
while(cin>>x>>z>>y){
wide=max(wide,y);
insert(1,10000,x,y-1,z,1);
}
query(1,10000,1);
for (int i=1;i<=wide;i++){
if (ans[i]==tem) continue;
cout<
 
 Share 【BZOJ 3132】上帝造题的七分钟 / 题解 BZOJ原题地址 [https://www.lydsy.com/JudgeOnline/problem.php?id=3132] 洛谷原题地址 [https:… 10 Jul 2018 【CodeForces 865G】Flowers and Chocolate / 题解 Origin [https://codeforces.com/problemset/problem/865/G] 题目描述 Idea 待整理。。。 Code… 09 Jul 2018 
 
 
 Zepto's © 2024 Data & privacy Contact → Published with Ghost • Theme Attila • System theme 
 $(document).ready(function () { var viewport =$(window); var post = $('.post-content'); // Responsive videos with fitVids post.fitVids(); // Format code blocks and add line numbers function codestyling() {$('pre code').each(function(i, e) { // Code highlight hljs.highlightElement(e); // No lines for plain text blocks if (!$(this).hasClass('language-text')) { var code =$(this); // Calculate amount of lines var lines = code.html().split(/\n(?!$)/g).length; var numbers = []; if (lines > 1) { lines++; } for (i = 1; i < lines; i++) { numbers += '<span class="line" aria-hidden="true">' + i + '</span>'; } code.parent().append('<div class="lines">' + numbers + '</div>'); } }); } codestyling(); // Reading progress bar on window top function readingProgress() { var postBottom = post.offset().top + post.height(); var viewportHeight = viewport.height(); var progress = 100 - (((postBottom - (viewport.scrollTop() + viewportHeight) + viewportHeight / 3) / (postBottom - viewportHeight + viewportHeight / 3)) * 100);$('.progress-bar').css('width', progress + '%'); (progress > 100) ? $('.progress-container').addClass('complete'):$('.progress-container').removeClass('complete'); } readingProgress(); // Trigger reading progress viewport.on({ 'scroll': function() { readingProgress(); }, 'resize': function() { readingProgress(); }, 'orientationchange': function() { readingProgress(); } }); });