제출 #229501

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
229501		tushar_2658	벽 (IOI14_wall)	C++14	100 / 100	1255 ms	99704 KiB

wall

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

const int maxn = 2000005;
int N, K;
int mn[maxn << 2], mx[maxn << 2], t[maxn << 2];

void applymn(int node, int h){
  mn[node] = min(mn[node], h); 
  mx[node] = min(mx[node], mn[node]);
}

void applymx(int node, int h){
  mx[node] = max(mx[node], h);
  mn[node] = max(mn[node], mx[node]);
}

void push_down(int node){
  applymn(2*node, mn[node]); 
  applymn(2*node + 1, mn[node]);
  applymx(2*node, mx[node]);
  applymx(2*node + 1, mx[node]);
  mn[node] = INT_MAX;
  mx[node] = 0;
}

void upd(int node, int b, int e, int i, int j, int val, int id){
  if(i > e || j < b)return;
  if(b >= i && j >= e){
    if(id == 1){
      applymx(node, val);
    }else {
      applymn(node, val);
    }
    return;
  }
  push_down(node);
  int mid = (b + e) >> 1;
  upd(2*node, b, mid, i, j, val, id);
  upd(2*node + 1, mid + 1, e, i, j, val, id);
}

int query(int node, int b, int e, int i){
  if(b == e){
    return min(max(0, mn[node]), mx[node]);
  }else {
    push_down(node);
    int mid = (b + e) >> 1;
    if(i <= mid){
      return query(2*node, b, mid, i);
    }else {
      return query(2*node + 1, mid + 1, e, i);
    }
  }
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  N = n, K = k;
  for(int i = 0; i < (maxn << 2); ++i){
    mn[i] = INT_MAX;
    mx[i] = 0;
  }
  for(int i = 0; i < K; ++i){
    upd(1, 1, N, left[i] + 1, right[i] + 1, height[i], op[i]);
  }
  for(int i = 1; i <= N; ++i){
    finalHeight[i - 1] = query(1, 1, N, i);
  }

  return;
}

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