Submission #1062922

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062922		YassirSalama	Wall (IOI14_wall)	C++17	100 / 100	1180 ms	214236 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;
  Node* left,*right;
  Node() : left(nullptr),right(nullptr){}
};
void pull(Node* node){
  //for min
  if (node->left->max == node->right->max) {
		node->max = node->left->max;
		node->smax = max(node->left->smax, node->right->smax);
	} else {
		if (node->left->max > node->right->max) {
			node->max = node->left->max;
			node->smax = max(node->left->smax, node->right->max);
		} else {
			node->max = node->right->max;
			node->smax = max(node->left->max, node->right->smax);
		}
	}
 
	// min
	if (node->left->min == node->right->min) {
		node->min = node->left->min;
		node->smin = min(node->left->smin, node->right->smin);
	} else {
		if (node->left->min < node->right->min) {
			node->min = node->left->min;
			node->smin = min(node->left->smin, node->right->min);
		} else {
			node->min = node->right->min;
			node->smin = min(node->left->min, node->right->smin);
		}
	}
}
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 p(Node* node,int l,int r){
  push(node,l,r);
  if(l==r) return;
  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){
    //put tag
    pmin(node,l,r,x);
    return;
  }
  p(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){
  p(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;
  }
  p(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: 29 / 29
• Subtask 4: 39 / 39