Submission #480145

#	Time	Username	Problem	Language	Result	Execution time	Memory
480145		Apiram	Wall (IOI14_wall)	C++14	0 / 100	262 ms	70660 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int64_t MXN = 1e6;
vector<int64_t>uptree(4*MXN);
vector<int64_t>downtree(4*MXN);
int64_t func(int64_t a,int64_t b){
return min(a,b);
}
void build(int64_t node,int64_t node_low,int64_t node_high){
	if (node_low==node_high){
		uptree[node]=0;
		downtree[node]=INT_MAX;
	}
	else {
		int64_t mid  =(node_low+node_high)>>1;
		build(node*2,node_low,mid);
		build(node*2 + 1,mid+1,node_high);
		uptree[node]=func(uptree[node*2],uptree[node*2 + 1]);	
		downtree[node]=func(downtree[node*2],downtree[node*2 + 1]);	
	}
}
void push(int64_t x){

            uptree[x + x] = max(uptree[x],uptree[x+x]);
            uptree[x + x + 1] = max(uptree[x],uptree[x+x + 1]);
            downtree[x + x] = min(downtree[x],downtree[x+x]);
            downtree[x + x + 1] = min(downtree[x],downtree[x+x+1]);
            uptree[x+x] = min(uptree[x+x],downtree[x]);
            uptree[x+x+1] = min(uptree[x+x+1],downtree[x]);
            downtree[x + x] = max(uptree[x],downtree[x+x]);
            downtree[x + x + 1] = max(uptree[x],downtree[x+x+1]);
            
        
}
void update(int64_t node,int64_t node_low,int64_t node_high,int64_t q_low,int64_t q_high,int64_t new_val,int ok){
	
	if (node_low>node_high||node_low>q_high||node_high<q_low)return;
	if (q_low<=node_low&&q_high>=node_high){
		if (ok==1){
			uptree[node] = max(uptree[node],new_val);
			downtree[node] = max(downtree[node],new_val);
		}
		else{
			uptree[node] = min(uptree[node],new_val);
			downtree[node] = min(downtree[node],new_val);
		}
		return ;
	}
	push(node);
	downtree[node]=INT_MAX, uptree[node]=0;
	int64_t mid = (node_low + node_high)/2;
	update(node*2,node_low,mid,q_low,q_high,new_val,ok);
	update(node*2  + 1,mid + 1,node_high,q_low,q_high,new_val,ok);
	downtree[node]= func(downtree[node*2],downtree[node*2 + 1]); 
	uptree[node]= func(uptree[node*2],uptree[node*2 + 1]); 

}
int64_t query(int64_t node,int64_t node_low,int64_t node_high,int64_t query_low,int64_t query_high){
	if (node_low>node_high||node_low>query_high||node_high<query_low)return 0;
	if (query_low<=node_low&&query_high>=node_high){
	return min(uptree[node],downtree[node]);
	}
	int64_t mid = (node_low+node_high)/2;
	return func(query(node*2,node_low,mid,query_low,query_high),query(node*2 + 1,mid+1,node_high,query_low,query_high));
}
void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	build(1,0,n-1);
  	for (int i =0;i<k;++i){
  		update(1,0,n-1,left[i],right[i],height[i],op[i]);
  	}
  	for (int i = 0;i<n;++i){
  		finalHeight[i] = query(1,0,n-1,i,i);
  	}
}

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