제출 #793187

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
793187		Ronin13	벽 (IOI14_wall)	C++17	100 / 100	601 ms	72996 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define ll long long 
#define ull unsigned ll
#define f first
#define s second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define epb emplace_back
using namespace std;
const int nmax = 2000001;
int l[nmax * 4], r[nmax * 4];


void upd(int a, int b){
    if(l[a] > r[b])
      l[b] = r[b] = l[a];
    else{
      if(r[a] < l[b])
        l[b] = r[b] = r[a];
      else{
          l[b] = max(l[a], l[b]);
          r[b] = min(r[a], r[b]);
      }
    }
}

void push(int v){
  upd(v, 2 * v);
  upd(v, 2 * v + 1);
}

void update(int v, int L, int R, int st, int fin, int val, int op){
  if(L > fin || R < st)
  return;
  if(L >= st && R <= fin){
      if(op == 1){
          l[v] = max(l[v], val);
          r[v] = max(r[v], l[v]);
      }
      else{
          r[v] = min(r[v], val);
          l[v] = min(r[v], l[v]);
      }
      return;
  }
  int m = (L + R) / 2;
  push(v);
  update(2 * v, L, m, st, fin, val, op);
  update(2 * v + 1, m + 1, R, st, fin, val, op);
  l[v] = min(l[2 * v], l[2 * v + 1]);
  r[v] = max(r[2 * v], r[2 * v + 1]);
}
int ans[nmax];
void get(int v, int L, int R){
    if(L == R){
      ans[L] = l[v];
      return;
    }
    int  M = (L + R) / 2;
    push(v);
    get(2 * v, L, M);
    get(2 * v + 1, M + 1, R);
}

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  
  for(int i = 0; i < k; i++){
      update(1, 0, n - 1, left[i], right[i], height[i], op[i]);
  }
  get(1, 0, n - 1);
  for(int i = 0; i < n; i++)
    finalHeight[i] = ans[i];
  return;
}

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