Submission #1062811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062811		YassirSalama	Wall (IOI14_wall)	C++17	32 / 100	3030 ms	21844 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 cntmin;
  int cntmax;
  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->min==node->left->min){
    if(node->min==node->right->min){
      node->cntmin=node->left->cntmin+node->right->cntmin;
      node->smin=min(node->left->smin,node->right->min);
    }else {
      node->smin=min({node->left->smin,node->right->min});
      node->cntmin=node->left->cntmin;
    }
  }else{
    node->smin=min({node->right->smin,node->left->min});
    node->cntmin=node->right->cntmin;
  }
  
  //for max
  node->max=max(node->left->max,node->right->max);
  if(node->max==node->left->max){
    if(node->max==node->right->max){
      node->cntmax=node->left->cntmax+node->right->cntmax;
      node->smax=max(node->left->smax,node->right->max);
    }else {
      node->smax=max({node->left->smax,node->right->max});
      node->cntmax=node->left->cntmax;
    }
  }else{
    node->smax=max({node->right->smax,node->left->max});
    node->cntmax=node->right->cntmax;
  }
  
  
  
  
}
void build(Node* node,int l,int r){
  if(l==r){
    node->min=node->max=0;
    node->cntmin=node->cntmax=1;
    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){
  if(node->smax<=node->lzmin&&node->lzmin<node->max){
    node->max=node->lzmin;
    node->min=min(node->min,node->lzmin);
    if(l==r) return;
    node->left->lazy=1;
    node->right->lazy=1;
    node->left->lzmin=node->lzmin;
    node->right->lzmin=node->lzmin;
  }
  return;
}
void pmax(Node* node,int l,int r){
  if(node->smin>=node->lzmax&&node->lzmax>node->min){
    node->min=node->lzmax;
    node->max=max(node->max,node->lzmax);
    if(l==r) return;
    node->left->lazy=1;
    node->right->lazy=1;
    node->left->lzmax=node->lzmax;
    node->right->lzmax=node->lzmax;
  }
  return;
}
void push(Node* node,int l,int r){
  if(node->lazy==false) return;
  if(node->lzmin!=-1){
    pmin(node,l,r);
  }
  if(node->lzmax!=-1){
    pmax(node,l,r);
  }
  node->lazy=false;
  node->lzmin=node->lzmax=-1;
  
}
void p(Node* node,int l,int r){
  push(node,l,r);
  if(l==r) return;
  push(node->left,l,(l+r)/2);
  push(node->right,(l+r)/2+1,r);
  pull(node);
}
void setmin(Node* node,int l,int r,int ql,int qr,int x){
  p(node,l,r);
  if(l>qr||r<ql) return;
  if(node->max<=x) return;
  if(ql<=l&&r<=qr&&node->smax<=x&&x<node->max){
    //put tag
    node->lazy=1;
    node->lzmin=x;
    p(node,l,r);
    return;
  }
  int mid=(l+r)/2;
  setmin(node->left,l,mid,ql,qr,x);
  setmin(node->right,mid+1,r,ql,qr,x);
  p(node,l,r);
}
void setmax(Node* node,int l,int r,int ql,int qr,int x){
  p(node,l,r);
  if(l>qr||r<ql) return;
  if(node->min>=x) return;
  if(ql<=l&&r<=qr&&node->smin>=x&&x>node->min){
    //put tag
    node->lazy=1;
    node->lzmax=x;
    p(node,l,r);
    return;
  }
  int mid=(l+r)/2;
  setmax(node->left,l,mid,ql,qr,x);
  setmax(node->right,mid+1,r,ql,qr,x);
  p(node,l,r);  
}
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