Submission #1149370

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149370		rayan_bd	Wall (IOI14_wall)	C++20	61 / 100	263 ms	11348 KiB

wall

#include <bits/stdc++.h>
using namespace std;

const int mxN = 2e5 + 500;
const int INF = 1e9;

struct seg_tree{
	struct Node{
		int mn=0,mx=INF;
	} seg[mxN*4];

	Node dummy,new_node;

	void apply(int node,Node v){
		seg[node].mn = max(seg[node].mn, v.mn);
		seg[node].mx = max(seg[node].mx, seg[node].mn);
		seg[node].mx = min(seg[node].mx, v.mx);
		seg[node].mn = min(seg[node].mn, seg[node].mx);
	}

	void push(int node){
		apply(node*2+1,seg[node]);
		apply(node*2+2,seg[node]);
		seg[node]=dummy;
	}

	void update(int node,int start,int end,int l,int r,Node nd){
		if(start>r||end<l) return;
		if(start>=l&&end<=r){
			apply(node,nd);
			return;
		}
		int mid=start+(end-start)/2;
		push(node);
		update(node*2+1,start,mid,l,r,nd);
		update(node*2+2,mid+1,end,l,r,nd);
	}

	int qry(int node,int start,int end,int idx){
		if(start==end) return seg[node].mn;
		int mid=start+(end-start)/2;
		push(node);
		if(idx<=mid) return qry(node*2+1,start,mid,idx);
		else return qry(node*2+2,mid+1,end,idx);
	}

} tr;


void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	for(int i=0;i<k;++i){
		if(op[i]==1){
			tr.new_node.mn=height[i];
    		tr.new_node.mx=INF;
    		tr.update(0,0,n-1,left[i],right[i],tr.new_node);
		}else{
			tr.new_node.mn=0;
    		tr.new_node.mx=height[i];
    		tr.update(0,0,n-1,left[i],right[i],tr.new_node);
		}
	}
	for(int i=0;i<n;++i){
		finalHeight[i]=tr.qry(0,0,n-1,i);
	}
}

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