제출 #365027

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
365027		kimbj0709	벽 (IOI14_wall)	C++14	100 / 100	1199 ms	138720 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
#define maxn 2000050
vector<int> seg(maxn*4,0);
vector<int> up(maxn*4,-1);
vector<int> down(maxn*4,INT_MAX);
vector<int> ans;
void push(int node){
  up[node*2+1] = max(up[node*2+1],up[node]);
  up[node*2+2] = max(up[node*2+2],up[node]);
  down[node*2+1] = max(down[node*2+1],up[node]);
  down[node*2+2] = max(down[node*2+2],up[node]);
  down[node*2+1] = min(down[node*2+1],down[node]);
  down[node*2+2] = min(down[node*2+2],down[node]);
  up[node*2+1] = min(up[node*2+1],down[node]);
  up[node*2+2] = min(up[node*2+2],down[node]);
  up[node] = -1;
  down[node] = INT_MAX;
}
void update(int node,int start,int end,int rangemin,int rangemax,int type,int val){
  //cout << node << " " << start << " " << end << ' ' << rangemin << ' ' << rangemax << " " << type << " "<< val << endl; 
  if(start>=rangemin&&end<=rangemax){
    //cout << " " << start " " 
    if(type==1){
      up[node] = max(up[node],val);
      down[node] = max(down[node],up[node]);
    }
    if(type==2){
      down[node] = min(down[node],val);
      up[node] = min(up[node],down[node]);
    }
    if(start==end){
      if(up[node]!=-1){
        seg[node] = max(seg[node],up[node]);
      }
      if(down[node]!=INT_MAX){
        seg[node] = min(seg[node],down[node]);
      }
      up[node] = -1;
      down[node] = INT_MAX;
    }
    return;
  }
  if(start==end){
    if(up[node]!=-1){
      seg[node] = max(seg[node],up[node]);
    }
    if(down[node]!=INT_MAX){
      seg[node] = min(seg[node],down[node]);
    }
    up[node] = -1;
    down[node] = INT_MAX;
    return;
  }
  if(start>rangemax||end<rangemin){
    //cout << " "<< start << " " << end << "---------\n";
    return;
  }
  push(node);
  int mid = (start+end)/2;
  update(node*2+1,start,mid,rangemin,rangemax,type,val);
  update(node*2+2,mid+1,end,rangemin,rangemax,type,val);
}
void print(int node,int start,int end){
  //cout << up[node] << " "<< down[node] << " " << start << " " << end << "--\n";
  if(start==end){
    if(up[node]!=-1){
      seg[node] = max(seg[node],up[node]);
    }
    if(down[node]!=INT_MAX){
      seg[node] = min(seg[node],down[node]);
    }
    up[node] = -1;
    down[node] = INT_MAX;
  }
  push(node);
  if(start==end){
    ans.push_back(seg[node]);
    return;
  }
  int mid = (start+end)/2;
  print(node*2+1,start,mid);
  print(node*2+2,mid+1,end);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  int a,b,c,d;
  for(int i=0;i<k;i++){
    a = op[i];
    b = left[i];
    c = right[i];
    d = height[i];
    update(0,0,n-1,b,c,a,d);
  }
  print(0,0,n-1);
  for(int i=0;i<n;i++){
    finalHeight[i] = ans[i];
  }
  return;
}

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