제출 #892900

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892900		Mr_Husanboy	Wall (IOI14_wall)	C++17	100 / 100	818 ms	78936 KiB

wall

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

using namespace std;
const int inf = 1e9;



struct Segtree{
  struct Node{
    int mn = inf, mx = 0;
    void apply(int x, int type){
      if(type == 1){
        mn = max(mn, x);
        mx = max(mx, x);
      }else{
        mn = min(mn, x);
        mx = min(mx, x);
      }
    }
    void calibrate(){
      mn = inf, mx = 0;
    }
  };
  vector<Node> t;
  int n;

  void init(int _n){
    n = _n;
    t.resize(4 * n);
  }

  void push(int x){
    t[x * 2].apply(t[x].mx, 1);
    t[x * 2].apply(t[x].mn, 2);
    t[x * 2 + 1].apply(t[x].mx, 1);
    t[x * 2 + 1].apply(t[x].mn, 2);
    t[x].calibrate();
  }

  void upd(int x, int l, int r, int ql, int qr, int val, int type){
    if(l > qr || ql > r) return;
    if(ql <= l && r <= qr){
      t[x].apply(val, type);
      return;
    } 
    push(x);
    int m = (l + r) / 2;
    upd(x * 2, l, m, ql, qr, val, type);
    upd(x * 2 + 1, m + 1, r, ql, qr, val, type);
  }

  int get(int x, int l, int r, int ind){
    if(l == r){
      return t[x].mx;
    }
    push(x);
    int m = (l + r) / 2;
    if(ind <= m) return get(x * 2, l, m, ind);
    else return get(x * 2 + 1, m + 1, r, ind);
  }

  //interface

  void upd(int l, int r, int val, int type){
    upd(1, 0, n - 1, l, r, val, type);
  }

  int get(int ind){
    return get(1, 0, n - 1, ind);
  }
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[]){
    Segtree t;
    t.init(n);
    for(int i = 0; i < k; i ++){
      t.upd(left[i], right[i], height[i], op[i]);
    }
    for(int i = 0; i < n; i ++) ans[i] = t.get(i);
}

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