Submission #1160803

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160803		hackstar	Wall (IOI14_wall)	C++17	0 / 100	0 ms	328 KiB

wall

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;

struct SegmentTree{
	int n;
	vector<int>treeMin,treeMax,lazyMin,lazyMax;
	SegmentTree(int size){
		n=size;
		treeMin.resize(4*n,INT_MAX);
		treeMax.resize(4*n,-INT_MAX);
		lazyMin.resize(4*n,-1);
		lazyMax.resize(4*n,-1);
	}
	void propagate(int node,int start,int end){
		if(lazyMin[node]!=-1){
			treeMin[node]=min(treeMin[node],lazyMin[node]);
			if(start!=end){
				lazyMin[2*node+1]=(lazyMin[2*node+1]==-1)?lazyMin[node]:min(lazyMin[2*node+1],lazyMin[node]);
				lazyMin[2*node+2]=(lazyMin[2*node+2]==-1)?lazyMin[node]:min(lazyMin[2*node+2],lazyMin[node]);
			}
			lazyMin[node]=-1;
		}
		if(lazyMax[node]!=-1){
			treeMax[node]=max(treeMax[node],lazyMax[node]);
			if(start!=end){
				lazyMax[2*node+1]=(lazyMax[2*node+1]==-1)?lazyMax[node]:max(lazyMax[2*node+1],lazyMax[node]);
				lazyMax[2*node+2]=(lazyMax[2*node+2]==-1)?lazyMax[node]:max(lazyMax[2*node+2],lazyMax[node]);
			}
			lazyMax[node]=-1;
		}
	}
	void update2Range(int node,int start,int end,int l,int r,int value){
		propagate(node,start,end);
		if(start>end||start>r||end<l)return;
		if(start>=l&&end<=r){
			lazyMin[node]=(lazyMin[node]==-1)?value:min(lazyMin[node],value);
			propagate(node,start,end);
			return;
		}
		int mid=(start+end)/2;
		update2Range(2*node+1,start,mid,l,r,value);
		update2Range(2*node+2,mid+1,end,l,r,value);
		treeMin[node]=min(treeMin[2*node+1],treeMin[2*node+2]);
	}
	void update1Range(int node,int start,int end,int l,int r,int value){
		propagate(node,start,end);
		if(start>end||start>r||end<l)return;
		if(start>=l&&end<=r){
			lazyMax[node]=(lazyMax[node]==-1)?value:max(lazyMax[node],value);
			propagate(node,start,end);
			return;
		}
		int mid=(start+end)/2;
		update1Range(2*node+1,start,mid,l,r,value);
		update1Range(2*node+2,mid+1,end,l,r,value);
		treeMax[node]=max(treeMax[2*node+1],treeMax[2*node+2]);
	}
	int queryMin(int node,int start,int end,int l,int r){
		propagate(node,start,end);
		if(start>end||start>r||end<l)return INT_MAX;
		if(start>=l&&end<=r)return treeMin[node];
		int mid=(start+end)/2;
		int left_query=queryMin(2*node+1,start,mid,l,r);
		int right_query=queryMin(2*node+2,mid+1,end,l,r);
		return min(left_query,right_query);
	}
	int queryMax(int node,int start,int end,int l,int r){
		propagate(node,start,end);
		if(start>end||start>r||end<l)return -INT_MAX;
		if(start>=l&&end<=r)return treeMax[node];
		int mid=(start+end)/2;
		int left_query=queryMax(2*node+1,start,mid,l,r);
		int right_query=queryMax(2*node+2,mid+1,end,l,r);
		return max(left_query,right_query);
	}
	void update2(int l,int r,int value){
		update2Range(0,0,n-1,l,r,value);
	}
	void update1(int l,int r,int value){
		update1Range(0,0,n-1,l,r,value);
	}
	int rangeQueryMin(int l,int r){
		return queryMin(0,0,n-1,l,r);
	}
	int rangeQueryMax(int l,int r){
		return queryMax(0,0,n-1,l,r);
	}
};

void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	SegmentTree st(n);
	for(int i=0;i<k;++i){
		int l=left[i], r=right[i], value = height[i];
		if(op[i] == 1){
			st.update1(l-1, r-1, value);
		}
		else if(op[i] == 2){
			st.update2(l-1, r-1, value);
		}
	}
	for(int i=0;i<n;++i){
		finalHeight[i] = st.rangeQueryMin(i, i);
	}
}

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