Submission #480151

#	Time	Username	Problem	Language	Result	Execution time	Memory
480151		Apiram	Wall (IOI14_wall)	C++14	0 / 100	200 ms	70724 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int64_t MXN = 1e6;
vector<int64_t>tree(4*MXN);
vector<int64_t>lazy(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){
		tree[node]=0;
	}
	else {
		int64_t mid  =(node_low+node_high)>>1;
		build(node*2,node_low,mid);
		build(node*2 + 1,mid+1,node_high);
		tree[node]=func(tree[node*2],tree[node*2 + 1]);	
	}
}
void push(int64_t x){
 
            tree[x + x] = min(tree[x],tree[x+x]);
            tree[x + x + 1] = min(tree[x],tree[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){
			tree[node] = max(tree[node],new_val);
		}
		else{
			tree[node] = min(tree[node],new_val);
		}
		return ;
	}
	push(node);
	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);
	tree[node]= func(tree[node*2],tree[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 INT_MAX;
	if (query_low<=node_low&&query_high>=node_high){
	return tree[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