Submission #530781

#	Time	Username	Problem	Language	Result	Execution time	Memory
530781		PoPularPlusPlus	Wall (IOI14_wall)	C++17	100 / 100	697 ms	64992 KiB

wall

#include <bits/stdc++.h>

using namespace std;

#include "wall.h"

struct item {
	int rem , fin;
};

struct Seg {
	int siz;
	vector<item> sum;
	
	item nutral = {INT_MAX , 0};
	
	item merge(item a , item b){
		item ans;
		ans.fin = max(a.fin , min(b.fin , a.rem));
		ans.rem = min(a.rem , b.rem);
		return ans;
	}
	
	void init(int n){
		siz = 1;
		while(siz < n)siz *= 2;
		sum.assign(siz * 2 , nutral);
	}
	
	vector<int> v;
	
	void set(int n , int x , int lx , int rx){
		if(rx - lx == 1){
			if(lx < n)v.push_back(sum[x].fin);
			return;
		}
		sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
		sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
		sum[x] = nutral;
		int m = (lx + rx)/2;
		set(n , 2 * x + 1 , lx , m);
		set(n , 2 * x + 2  , m , rx);
	}
	
	vector<int> setall(int n){
		v.clear();
		set(n , 0 , 0 , siz);
		return v;
	}
	
	void range_set(int l, int r , int op , int h , int x , int lx , int rx){
		if(rx <= l || lx >= r){
			return;
		}
		if(lx >= l && rx <= r){
			if(op == 2){
				sum[x].fin = min(sum[x].fin , h);
				sum[x].rem = min(sum[x].rem , h);
			}
			else sum[x].fin = max(sum[x].fin , h);
			return;
		}
		sum[2 * x + 1] = merge(sum[x] , sum[2 * x + 1]);
		sum[2 * x + 2] = merge(sum[x] , sum[2 * x + 2]);
		sum[x] = nutral;
		int m = (lx + rx)/2;
		range_set(l , r , op , h , 2 * x + 1 , lx , m);
		range_set(l ,r , op , h , 2 * x + 2 , m, rx);
	}
	
	void range_set(int l , int r , int op , int h){
		range_set(l , r , op , h , 0 , 0 , siz);
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int hei[], int finalHeight[]){
  Seg st;
  st.init(n);
  for(int i = 0; i < k; i++){
	  st.range_set(left[i] , right[i]+1 , op[i] , hei[i]);
  }
  vector<int> v = st.setall(n);
  for(int i = 0; i < n; i++)finalHeight[i] = v[i];
}

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