Submission #428979

#	Time	Username	Problem	Language	Result	Execution time	Memory
428979		MeGustaElArroz23	Wall (IOI14_wall)	C++14	100 / 100	2273 ms	149600 KiB

wall

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

///////

#include "wall.h"
#include<bits/stdc++.h>

using namespace std;

typedef vector<int> vi;
typedef pair<int,int> pii;

int INF=2000000000;

struct node{
    int l;
    int r;
    int left;
    int right;
    pii minmax;
};

pii combine(pii a, pii b){ // a antes que b
	pii res;	
    res.first=max(a.first,b.first);
    res.second=min(a.second,b.second);
    if (res.first>res.second){
		if(a.first<b.first) res.second=res.first;
		else res.first=res.second;
    }
//cerr << a.first << ' '<<a.second << ' '<<b.first<<' '<<b.second<<' '<<res.first<<' '<<res.second<<'\n';

	return res;
}

int counter=0;
vector<node> st(5000000);

void create_tree(int l, int r){
	int ac=counter;
	st[ac].l=l;
	st[ac].r=r;
	st[ac].minmax=pii{0,0};
	if (l!=r){
		//st[ac].minmax=pii{0,INF};
		counter++;
		st[ac].left=counter;
		create_tree(l,(l+r)/2);
		counter++;
		st[ac].right=counter;
		create_tree((l+r)/2+1,r);
	}
}

void push_tree(int ac, int l, int r, pii x){
	if (l==st[ac].l and r==st[ac].r){
		st[ac].minmax=combine(st[ac].minmax,x);
		return;
	}
	else{
		push_tree( st[ac].left , st[ac].l , (st[ac].l+st[ac].r)/2 , st[ac].minmax );
		push_tree( st[ac].right , (st[ac].l+st[ac].r)/2+1 , st[ac].r , st[ac].minmax );

		st[ac].minmax=pii{0,INF};

		int med=(st[ac].l+st[ac].r)/2;
		if (l>med){
			push_tree(st[ac].right , l , r , x);
		}
		else if (r<=med){
			push_tree(st[ac].left , l , r , x);
		}
		else{
			push_tree( st[ac].left , l , med , x );
			push_tree( st[ac].right, med+1 , r , x);
		}
		return;
	}
}

void buildWall(int n, int k, int type[], int left[], int right[], int height[], int finalHeight[]){
	create_tree(0,n-1);
	for (int i=0;i<k;i++){
		if (type[i]==1){
			push_tree(0,left[i],right[i],pii{height[i],INF});
		}
		else{
			push_tree(0,left[i],right[i],pii{0,height[i]});
		}
	//for (int x=0;x<n;x++){
	//	push_tree(0,x,x,pii{0,INF});
	//}
	
	//int x=0;
	//int j=0;
	//while (x<n){
	//	if (st[j].l==st[j].r){
	//		//cerr << st[j].l << ' '<<st[j].minmax.first<<'\n';
	//		x++;
	//	}
	//	j++;
	//}
	}
	
	for (int x=0;x<n;x++){
		push_tree(0,x,x,pii{0,INF});
	}
	int i=0;
	int j=0;
	while (i<n){
		if (st[j].l==st[j].r){
			finalHeight[st[j].l]=st[j].minmax.first;
			i++;
		}
		j++;
	}
    return;
}

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