제출 #841738

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
841738		12345678	벽 (IOI14_wall)	C++17	100 / 100	552 ms	99464 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=2e6+5;

struct segtree
{
  struct node
  {
    int low, up;
    node(): low(0), up(INT_MAX){}
  } d[4*nx];
  void add(int l, int r, int i, int ql, int qr, int t)
  {
    if (qr<l||r<ql) return;
    t=max(t, d[i].low);
    t=min(t, d[i].up);
    if (ql<=l&&r<=qr) return void(d[i].low=t);
    int md=(l+r)/2;
    add(l, md, 2*i, ql, qr, t);
    add(md+1, r, 2*i+1, ql, qr, t);
  }
  void remove(int l, int r, int i, int ql, int qr, int t)
  {
    if (qr<l||r<ql) return;
    t=max(t, d[i].low);
    t=min(t, d[i].up);
    if (ql<=l&&r<=qr) return void(d[i].up=t);
    int md=(l+r)/2;
    remove(l, md, 2*i, ql, qr, t);
    remove(md+1, r, 2*i+1, ql, qr, t);
  }
  int query(int l, int r, int i, int idx, int t)
  {
    t=max(t, d[i].low);
    t=min(t, d[i].up);
    if (l==r) return t;
    int md=(l+r)/2;
    if (idx<=md) return query(l, md, 2*i, idx, t);
    else return query(md+1, r, 2*i+1, idx, t);
  }
} s;

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for (int i=k-1; i>=0; i--)
  {
    if (op[i]==1) s.add(0, n-1, 1, left[i], right[i], height[i]);
    else s.remove(0, n-1, 1, left[i], right[i], height[i]);
  }
  for (int i=0; i<n; i++) finalHeight[i]=s.query(0, n-1, 1, i, 0);
}

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