제출 #70866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
70866		doowey	Wall (IOI14_wall)	C++14	100 / 100	1092 ms	191700 KiB

wall

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

using namespace std;

const int N = 2000101;

struct Node{
  int min_op;
  int max_op;
};

Node Tree[N * 3];

void init(int node, int cl, int cr){
  Tree[node].min_op = (int)1e9 + 9;
  Tree[node].max_op = 0;
  if(cl == cr){
    return;
  }
  int md = (cl + cr)/2;
  init(node * 2, cl, md);
  init(node * 2 + 1, md + 1, cr);

}

void maxi(int node, int x){ // apply max(node)
  Tree[node].max_op = max(Tree[node].max_op, x);
  Tree[node].min_op = max(Tree[node].min_op, Tree[node].max_op);
}

void mini(int node, int x){ // apply min(node)
  Tree[node].min_op = min(Tree[node].min_op, x);
  Tree[node].max_op = min(Tree[node].max_op, Tree[node].min_op);
}

void push(int node, int tl, int tr){
  maxi(node * 2, Tree[node].max_op);
  maxi(node * 2 + 1, Tree[node].max_op);
  mini(node * 2, Tree[node].min_op);
  mini(node * 2 + 1, Tree[node].min_op);
  Tree[node].max_op = 0;
  Tree[node].min_op = (int)1e9 + 9;
}

void update(int node, int cl, int cr, int tl, int tr, int x, int op){
  if(cr < tl)
    return;
  if(cl > tr)
    return;
  if(cl >= tl and cr <= tr){
    if(op == 1)
      maxi(node, x);
    else
      mini(node, x);
    return;
  }
  push(node, cl, cr);
  int md = (cl + cr)/2;
  update(node*2, cl, md, tl, tr, x, op);
  update(node*2+1, md + 1, cr, tl, tr, x, op);
}

int fin[N];

void ff(int node, int cl, int cr){
  if(cl == cr){
    fin[cl] = Tree[node].max_op;
    return;
  }
  push(node, cl, cr);
  int md = (cl + cr)/2;
  ff(node * 2, cl, md);
  ff(node * 2 + 1, md + 1, cr);
}

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

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