제출 #1086228

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1086228		belgianbot	벽 (IOI14_wall)	C++17	100 / 100	794 ms	169916 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

vector<pair <pair <int,int>, pair<int,int> > > t;
void add(int i, int h, int ph){
  if (i == 24) {
    cin.tie(0);
  }
  if (t[i].se.se == -1) {
    t[i].se = {h, ph};
    return;
  }
  if (t[i].se.se != ph) {
    swap(t[i].fi, t[i].se);
    if (ph == 1) {
      t[i].se.fi = min(t[i].se.fi, t[i].fi.fi);
    }
    else t[i].se.fi = max(t[i].se.fi, t[i].fi.fi);
  }
  if (ph == 1) t[i].se.fi = max(t[i].se.fi, h);
  else t[i].se.fi = t[i].se.se == -1 ? h : min(t[i].se.fi, h);
  t[i].se.se = ph;
}
void merge(int i){
  
  if (t[i].fi.se != -1) {
    add(i * 2, t[i].fi.fi, t[i].fi.se);
    add(i * 2 + 1, t[i].fi.fi, t[i].fi.se);
  }
  if (t[i].se.se != -1) {
    add(i * 2, t[i].se.fi, t[i].se.se);
    add(i * 2 + 1, t[i].se.fi, t[i].se.se);
  }
  t[i] = { {0, -1}, {0, -1}};
}
void update(int i, int l, int r, int Ql, int Qr, int h, int ph) {
  if (l != r) merge(i);
  if (l > Qr || r < Ql) return;
  if (l >= Ql && r <= Qr) {
    add(i, h, ph);
    return;
  }
  
  int mid = (l + r) / 2;
  update(i * 2, l, mid, Ql, Qr, h, ph);
  update(i * 2 + 1, mid + 1, r, Ql, Qr, h, ph);
}

vector<int> ans;

void Query(int i, int l, int r) {
  if (l == r) {
    auto x = t[i];
    if (x.se.se == 1) ans[l] = x.se.fi;
    else ans[l] = min(x.fi.fi, x.se.fi);
    return;
  }
  int mid = (l + r) / 2;

  merge(i);
  Query(i * 2, l, mid);
  Query(i * 2 + 1, mid + 1, r);
}

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

  Query(1, 0, n-1);
  for (int i = 0; i < n; i++) {
    finalHeight[i] = ans[i];
  }
}

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