Submission #1082497

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082497		4QT0R	Wall (IOI14_wall)	C++17	0 / 100	28 ms	33220 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
#define pii pair<int,int>

const int base=1<<21;
pii tree[2*base];
int ans[2000003];

void lazy_prop(int v){
	if (v>=base)return;
	tree[2*v].first=max(tree[2*v].first,tree[v].first);
	tree[2*v].second=min(tree[2*v].second,tree[v].second);
	tree[2*v+1].first=max(tree[2*v+1].first,tree[v].first);
	tree[2*v+1].second=min(tree[2*v+1].second,tree[v].second);
	tree[v]={min(tree[2*v].first,tree[2*v+1].first),max(tree[2*v].second,tree[2*v+1].second)};
}

void update(int v, int l, int p, int a, int b, pii op){
	if (a<=l && p<=b){
		if (op.first==0){
			tree[v].first=max(tree[v].first,op.second);
			tree[v].second=max(tree[v].second,tree[v].first);
		}
		else{
			tree[v].second=min(tree[v].second,op.second);
			tree[v].first=min(tree[v].second,tree[v].first);
		}
		lazy_prop(v);
		return;
	}
	else if (p<a || b<l){
		lazy_prop(v);
		return;
	}
	else{
		lazy_prop(v);
		update(2*v,l,(l+p)/2,a,b,op);
		update(2*v+1,(l+p)/2+1,p,a,b,op);
		tree[v]={min(tree[2*v].first,tree[2*v+1].first),max(tree[2*v].second,tree[2*v+1].second)};
	}
}

void finalProp(int v){
	if (v>=base)return;
	lazy_prop(v);
	finalProp(2*v);
	finalProp(2*v+1);
}

void buildWall(int n, int k, int op[], int left[], int right[],int height[], int finalHeight[]){
	for (int i = 0; i<k; i++)update(1,0,base-1,left[i],right[i],{op[i],height[i]});
	finalProp(1);
	for (int i = 0; i<n; i++)finalHeight[i]=tree[base+i].first;
}

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