Submission #1062897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062897		YassirSalama	Wall (IOI14_wall)	C++17	32 / 100	3095 ms	23632 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
struct Node{
  int min;
  int max;
  int smin;
  int smax;
} tree[4*maxn];
void pull(int node){
  //for min
  tree[node].min=min(tree[node*2].min,tree[node*2+1].min);
  if(tree[node*2].min==tree[node*2+1].min){
    tree[node].smin=min(tree[node*2].smin,tree[node*2+1].smin);
  }else if(tree[node*2].min==tree[node].min){
    tree[node].smin=min(tree[node*2].smin,tree[node*2+1].min);
  }else tree[node].smin=min(tree[node*2+1].smin,tree[node*2].min);
  //for max
  tree[node].max=max(tree[node*2].max,tree[node*2+1].max);
  if(tree[node*2].max==tree[node*2+1].max){
    tree[node].smax=max(tree[node*2].smax,tree[node*2+1].max);
  }else if(tree[node*2].max==tree[node].max){
    tree[node].smax=max(tree[node*2].smax,tree[node*2+1].max);
  }else tree[node].smax=max(tree[node*2+1].smax,tree[node*2].max);
}
void build(int node,int l,int r){
  if(l==r){
    tree[node].min=tree[node].max=0;
    tree[node].smin=1e9;
    tree[node].smax=-1e9;
    return;
  }
  int mid=(l+r)/2;
  build(node*2,l,mid);
  build(node*2+1,mid+1,r);
  pull(node);
}
void pmin(int node,int l,int r,int x){
  if(tree[node].max<=x) return;
  tree[node].max=x;
  if(l==r){
    tree[node].min=tree[node].max;
  }else{
    if(x<=tree[node].min){
      tree[node].min=x;
    }else if(x<tree[node].smin){
      tree[node].smin=x;
    }
  }
}
void pmax(int node,int l,int r,int x){
  if(tree[node].min>=x)
    return;
  tree[node].min=x;
  if(l==r){
    tree[node].max=tree[node].min;
  }else{
    if(x>=tree[node].max){
      tree[node].max=x;
    }else if(x>tree[node].smax){
      tree[node].smax=x;
    }
  }
}
void push(int node,int l,int r){
  if(l==r) return;
  pmin(node*2,l,(l+r)/2,tree[node].max);
  pmin(node*2+1,(l+r)/2+1,r,tree[node].max);
  pmax(node*2,l,(l+r)/2,tree[node].min);
  pmax(node*2+1,(l+r)/2+1,r,tree[node].min);
}
void setmin(int node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql||tree[node].max<=x) return;
  if(ql<=l&&r<=qr&&tree[node].smax<x){
    //put tag
    pmin(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmin(node*2,l,mid,ql,qr,x);
  setmin(node*2+1,mid+1,r,ql,qr,x);
  pull(node);
}
void setmax(int node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql||tree[node].min>=x) return;
  if(ql<=l&&r<=qr&&x<tree[node].smin){
    //put tag
    pmax(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmax(node*2,l,mid,ql,qr,x);
  setmax(node*2+1,mid+1,r,ql,qr,x);
  pull(node);
}
int query(int node,int l,int r,int ql){
  push(node,l,r);
  if(l==r) return tree[node].min;
  int mid = (l+r)/2;
  if(ql<=mid) return query(node*2,l,mid,ql);
  else return query(node*2+1,mid+1,r,ql);
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int ans[])
{
  Node* root=new Node();
  build(1,0,n-1);
  for(int i=0;i<k;i++){
    int t=op[i];
    int l=left[i];
    int r=right[i];
    int x=height[i];
    if(t==1){
      setmax(1,0,n-1,l,r,x);
    }else{
      setmin(1,0,n-1,l,r,x);
    }
  }
  for(int i=0;i<n;i++){
    ans[i]=query(1,0,n-1,i);
  }
  return;
}

Compilation message (stderr)

wall.cpp: In function 'void buildWall(int, int, int*, int*, int*, int*, int*)':
wall.cpp:110:9: warning: unused variable 'root' [-Wunused-variable]
  110 |   Node* root=new Node();
      |         ^~~~

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