Submission #1104269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104269		vjudge1	Wall (IOI14_wall)	C++14	100 / 100	584 ms	100252 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
struct node{
  int mi;
  node() : mi(0) {}
}sg[8000005];
int lazy1[8000005],lazy2[8000005];
void push(int u,int l,int r)
{
  if(lazy1[u]!=-1)
  {
    sg[u].mi = max(sg[u].mi,lazy1[u]);
    if(l!=r)
    {
      lazy1[2*u] = max(lazy1[2*u],lazy1[u]);
      lazy2[2*u] = max(lazy2[2*u],lazy1[u]);
  
      lazy1[2*u+1] = max(lazy1[2*u+1],lazy1[u]);
      lazy2[2*u+1] = max(lazy2[2*u+1],lazy1[u]); 
        
    }
    lazy1[u] = -1;  
  }
  if(lazy2[u]!=2e9)
  {
    sg[u].mi = min(sg[u].mi,lazy2[u]);
    if(l!=r)
    {
      lazy1[2*u] = min(lazy1[2*u],lazy2[u]);
      lazy2[2*u] = min(lazy2[2*u],lazy2[u]);

      lazy1[2*u+1] = min(lazy1[2*u+1],lazy2[u]);
      lazy2[2*u+1] = min(lazy2[2*u+1],lazy2[u]);
    }
    lazy2[u] = 2e9; 
  }
}


void update_max(int u,int l,int r,int sl,int sr ,int x)
{
  push(u,l,r);
  if(l>r or l>sr or r<sl) return;
  if(sl<=l and r<=sr) 
  {

    lazy1[u] = x;
    push(u,l,r);
    return;
  }
  int m=(l+r)/2;
  update_max(2*u,l,m,sl,sr,x);
  update_max(2*u+1,m+1,r,sl,sr,x);
}
void update_min(int u,int l,int r,int sl,int sr ,int x)
{
  push(u,l,r);
  if(l>r or l>sr or r<sl) return;
  if(sl<=l and r<=sr)
  {
    lazy2[u] = x;
    push(u,l,r);
    return;
  }
  int m=(l+r)/2;
  update_min(2*u,l,m,sl,sr,x);
  update_min(2*u+1,m+1,r,sl,sr,x);
}
int ans[8000005];
void query(int u,int l,int r)
{
  push(u,l,r);
  if(r<l) return;
  if(l==r)
  {
    ans[l-1] = sg[u].mi;
    return ;
  }
  int m=(l+r)/2;
  query(2*u,l,m);
  query(2*u+1,m+1,r);
  
}
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_max(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    else
    {
      update_min(1,1,n,left[i]+1,right[i]+1,height[i]);
    }
    
  }
  query(1,1,n);
  
  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