Submission #1062888

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062888		YassirSalama	Wall (IOI14_wall)	C++17	32 / 100	3072 ms	29780 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e6 + 100;
template<typename T>
void dbg(const T& t){
  cout<<t<<endl;
  return;
}
template<typename T,typename... Args>
void dbg(const T& t,const Args&... args){
  cout<<t<<" , ";
  dbg(args...);
}
#define dbg(...) cout<<"("<<#__VA_ARGS__<<") : "<<endl;dbg(__VA_ARGS__);

struct Node
{
  int min;
  int max;
  int smin;
  int smax;
  int lzmin=-1,lzmax=-1;
  bool lazy=false;
  Node* left,*right;
  Node() : left(nullptr),right(nullptr){}
};
void pull(Node* node){
  //for min
  node->min=min(node->left->min,node->right->min);
  if(node->left->min==node->right->min){
    node->smin=min(node->left->smin,node->right->smin);
  }else if(node->left->min==node->min){
    node->smin=min(node->left->smin,node->right->min);
  }else node->smin=min(node->right->smin,node->left->min);
  
  //for max
  node->max=max(node->left->max,node->right->max);
  if(node->left->max==node->right->max){
    node->smax=max(node->left->smax,node->right->max);
  }else if(node->left->max==node->max){
    node->smax=max(node->left->smax,node->right->max);
  }else node->smax=max(node->right->smax,node->left->max);
}
void build(Node* node,int l,int r){
  if(l==r){
    node->min=node->max=0;
    node->smin=1e9;
    node->smax=-1e9;
    return;
  }
  int mid=(l+r)/2;
  node->left=new Node();
  node->right=new Node();
  build(node->left,l,mid);
  build(node->right,mid+1,r);
  pull(node);
}
void pmin(Node* node,int l,int r,int x){
  if(node->max<=x) return;
  node->max=x;
  if(l==r){
    node->min=node->max;
  }else{
    if(x<=node->min){
      node->min=x;
    }else if(x<node->smin){
      node->smin=x;
    }
  }
}
void pmax(Node* node,int l,int r,int x){
  if(node->min>=x)
    return;
  node->min=x;
  if(l==r){
    node->max=node->min;
  }else{
    if(x>=node->max){
      node->max=x;
    }else if(x>node->smax){
      node->smax=x;
    }
  }
}
void push(Node* node,int l,int r){
  if(l==r) return;
  pmin(node->left,l,(l+r)/2,node->max);
  pmin(node->right,(l+r)/2+1,r,node->max);
  pmax(node->left,l,(l+r)/2,node->min);
  pmax(node->right,(l+r)/2+1,r,node->min);
}
void setmin(Node* node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql) return;
  if(node->max<=x) return;
  if(ql<=l&&r<=qr&&node->smax<x){
    //put tag
    pmin(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmin(node->left,l,mid,ql,qr,x);
  setmin(node->right,mid+1,r,ql,qr,x);
  pull(node);
}
void setmax(Node* node,int l,int r,int ql,int qr,int x){
  push(node,l,r);
  if(l>qr||r<ql) return;
  if(node->min>=x) return;
  if(ql<=l&&r<=qr&&x<node->smin){
    //put tag
    pmax(node,l,r,x);
    return;
  }
  push(node,l,r);
  int mid=(l+r)/2;
  setmax(node->left,l,mid,ql,qr,x);
  setmax(node->right,mid+1,r,ql,qr,x);
  pull(node);
}
int query(Node* node,int l,int r,int ql){
  push(node,l,r);
  if(l==r) return node->min;
  int mid = (l+r)/2;
  if(ql<=mid) return query(node->left,l,mid,ql);
  else return query(node->right,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(root,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(root,0,n-1,l,r,x);
    }else{
      setmin(root,0,n-1,l,r,x);
    }
  }
  for(int i=0;i<n;i++){
    ans[i]=query(root,0,n-1,i);
  }
  return;
}

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