Submission #670792

#	Time	Username	Problem	Language	Result	Execution time	Memory
670792		mseebacher	Wall (IOI14_wall)	C++17	0 / 100	1 ms	428 KiB

wall

#include <bits/stdc++.h>
#include "wall.h"
using namespace std;
 
typedef long long ll;
typedef vector<int> vi;
#define MAXI (int)1e5

struct segtree{
	
	int size;
	vector<int> tree;
	vector<bool> marked;
	void init(int n){
		int x = 1;
		while(x < n) x*=2;
		size = x;
		tree.assign(2*size,0);
		marked.assign(2*size,0);
	}
	
	void pushMin(int v){
		if(marked[v]){
			tree[2*v+1] = min(tree[v],tree[2*v+1]);
			tree[2*v+2] = min(tree[v],tree[2*v+2]);
			marked[v] = false;
			marked[2*v+1] = marked[2*v+2] = true;
		}
	}
	
	void pushMax(int v){
		if(marked[v]){
			tree[2*v+1] = max(tree[v],tree[2*v+1]);
			tree[2*v+2] = max(tree[v],tree[2*v+2]);
			marked[v] = false;
			marked[2*v+1] = marked[2*v+2] = true;
		}
	}
	
	void maximize(int val,int l,int r,int x,int lx,int rx){
		if(l > r) return;
		if(l == lx && r == rx){
			tree[x] = max(tree[x],val);
			marked[x] = 1;
		}else{
			pushMax(x);
			int mid = (lx+rx)/2;
			maximize(val,l,r,2*x+1,lx,mid);
			maximize(val,l,r,2*x+2,mid,rx);
		}
	}
	
	void maximize(int val,int l,int r){
		maximize(val,l,r,0,0,size);
	}
	
	void minimize(int val,int l,int r,int x,int lx,int rx){
		if(l > r) return;
		if(l == lx && r == rx){
			tree[x] = min(tree[x],val);
			marked[x] = 1;
		}else{
			pushMin(x);
			int mid = (lx+rx)/2;
			minimize(val,l,r,2*x+1,lx,mid);
			minimize(val,l,r,2*x+2,mid,rx);
		}
	}
	
	void minimize(int val,int l,int r){
		minimize(val,l,r,0,0,size);
	}
	
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[],int finalHeight[]){
	segtree s;
	s.init(n);
	for(int i = 0;i<k;i++){
		if(op[i] == 1){
			s.maximize(height[i],left[i],right[i]);
		}else{
			s.minimize(height[i],left[i],right[i]);
		}
	}
	int ptr = s.size/2-1;
	for(int i = 0;i<n;i++){
		finalHeight[i] = s.tree[ptr++];
	}
	
}

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