Submission #597472

#	Time	Username	Problem	Language	Result	Execution time	Memory
597472		chirathnirodha	벽 (IOI14_wall)	C++17	100 / 100	613 ms	118100 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
#define PB push_back
#define MP make_pair
#define F first 
#define S second
#define P push
typedef long long ll;
const int maxn=2000000;
ll mini[maxn*4];
ll maxi[maxn*4];
ll finh[maxn];
void update_seg(ll c,ll l,ll h){
  if(maxi[c]<=l)mini[c]=maxi[c]=l;
  else if(mini[c]>=h)mini[c]=maxi[c]=h;
  else{
    maxi[c]=min(maxi[c],h);
    mini[c]=max(mini[c],l);
  }
}
void update(ll a,ll b,ll c,ll l,ll h,ll x,ll y){
  if(a==x && b==y){
    update_seg(c,l,h);
    return;
  }
  update_seg(2*c,mini[c],maxi[c]);
  update_seg(2*c+1,mini[c],maxi[c]);
  mini[c]=0;maxi[c]=INT32_MAX;
  ll m=(a+b)/2;
  if(y<=m)update(a,m,2*c,l,h,x,y);
  else if(x>m)update(m+1,b,2*c+1,l,h,x,y);
  else{
    update(a,m,2*c,l,h,x,m);
    update(m+1,b,2*c+1,l,h,m+1,y);
  }
}
void finalize(ll a,ll b,ll c){
  if(a==b){finh[a]=mini[c];return;}
  ll m=(a+b)/2;
  update_seg(2*c,mini[c],maxi[c]);
  update_seg(2*c+1,mini[c],maxi[c]);
  finalize(a,m,2*c);
  finalize(m+1,b,2*c+1);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
  for(int i=0;i<k;i++){
    if(op[i]==1)update(0,n-1,1,height[i],INT32_MAX,left[i],right[i]);
    else update(0,n-1,1,0,height[i],left[i],right[i]);
  }
  finalize(0,n-1,1);
  for(int i=0;i<n;i++)finalHeight[i]=finh[i];
  return;
}

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