제출 #1023500

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1023500		HappyCapybara	Wall (IOI14_wall)	C++17	100 / 100	671 ms	99476 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;

int N;
vector<pair<int,int>> lazy;

void merge(int node, pair<int,int> p){
  if (p.second >= lazy[node].first && lazy[node].second >= p.first){
    lazy[node].first = max(lazy[node].first, p.first);
    lazy[node].second = min(lazy[node].second, p.second);
    return;
  }
  if (p.first > lazy[node].second) lazy[node] = {p.first, p.first};
  else lazy[node] = {p.second, p.second};
  return;
}

void prop(int node){
  merge(node*2, lazy[node]);
  merge(node*2+1, lazy[node]);
  lazy[node] = {0, 100000};
  return;
}

void update(int l, int r, pair<int,int> p, int node=1, int tl=0, int tr=N-1){
  if (l <= tl && tr <= r){
    merge(node, p);
    return;
  }
  prop(node);
  int tm = (tl+tr)/2;
  if (l <= tm) update(l, r, p, node*2, tl, tm);
  if (tm+1 <= r) update(l, r, p, node*2+1, tm+1, tr);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = n;
  lazy.resize(4*n, {0, 100000});
  for (int i=0; i<k; i++){
    if (op[i] == 1) update(left[i], right[i], {height[i], 100000});
    else update(left[i], right[i], {0, height[i]});
  }
  for (int i=0; i<n; i++){
    finalHeight[i] = 0;
    int cur = 1, tl = 0, tr = n-1;
    while (tl != tr){
        int tm = (tl+tr)/2;
        if (i <= tm){
            cur = cur*2;
            tr = tm;
        }
        else {
            cur = cur*2+1;
            tl = tm+1;
        }
    }
    while (cur){
      if (finalHeight[i] < lazy[cur].first) finalHeight[i] = lazy[cur].first;
      if (finalHeight[i] > lazy[cur].second) finalHeight[i] = lazy[cur].second;
      cur >>= 1;
    }
  }
  return;
}

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