제출 #1284147

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1284147		DeltaStruct	벽 (IOI14_wall)	C++20	100 / 100	405 ms	63048 KiB

wall

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

void buildWall(int n,int q,int op[],int left[],int right[],int height[],int finalHeight[]){
  vector<tuple<int,int,int>> segtree(2*n,make_tuple(-1,1e9,-2));
  auto f = [&](tuple<int,int,int> x,tuple<int,int,int> y) -> tuple<int,int,int> {
    auto& [a,b,c] = x; auto [d,e,f] = y;
    if (a<b){
      if (d>=e) c = f;
      else if (b<=d) c = d;
      else if (e<=a) c = e;
    } else {
      if (d>=e) c = f;
      else if (c<=d) c = d;
      else if (e<=c) c = e;
    }
    a = max(a,d),b = min(b,e);
    return x;
  };
  auto pass = [&](int x) -> void {
    if (x<n) segtree[x<<1] = f(segtree[x<<1],segtree[x]),segtree[x<<1|1] = f(segtree[x<<1|1],segtree[x]);
    segtree[x] = make_tuple(-1,1e9,-2);
  };
  for (int i(0);i < q;++i){
    for (int l(21);l;--l) pass((n+left[i])>>l),pass((n+right[i])>>l);
    tuple<int,int,int> Q = make_tuple(-1,1e9,-2);
    if (op[i]==1) get<0>(Q) = height[i];
    else get<1>(Q) = height[i];
    for (int l(n+left[i]),r(n+right[i]+1);l < r;l>>=1,r>>=1){
      if (l&1) segtree[l] = f(segtree[l],Q),++l;
      if (r&1) --r,segtree[r] = f(segtree[r],Q);
    }
  }
  for (int i(1);i < n;++i) pass(i);
  for (int i(0);i < n;++i){
    auto [a,b,c] = segtree[n+i];
    finalHeight[i] = (a>=b?c:min(max(0,a),b));
  }
}

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