Submission #779815

#	Time	Username	Problem	Language	Result	Execution time	Memory
779815		YassirSalama	Wall (IOI14_wall)	C++14	100 / 100	618 ms	69524 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
// #define int long long
const int MAXN=2e6;
const int INF=1e9+7;
struct Node{
	int mn;
	int mx;
};
Node tree[4*MAXN];
void build(int node,int l,int r){
	tree[node].mn=INF;
	tree[node].mx=-INF;
	if(l==r) return;
	int mid=(l+r)/2;
	build(node<<1,l,mid);
	build(node<<1|1,mid+1,r);
}
void push(int node,int l,int r){
	if(l==r) return;
	int left=node<<1;
	int right=left|1;
	tree[left].mn=min(tree[node].mn,tree[left].mn);
	tree[left].mn=max(tree[node].mx,tree[left].mn);
	tree[left].mx=min(tree[node].mn,tree[left].mx);
	tree[left].mx=max(tree[node].mx,tree[left].mx);
	tree[right].mn=min(tree[node].mn,tree[right].mn);
	tree[right].mn=max(tree[node].mx,tree[right].mn);
	tree[right].mx=min(tree[node].mn,tree[right].mx);
	tree[right].mx=max(tree[node].mx,tree[right].mx);
	// tree[node].mn=INF;
	// tree[node].mx=-INF;
}
void update(int node,int l,int r,int ql,int qr,int x,int t){
	push(node,l,r);
	if(ql>r||qr<l) return;
	if(ql<=l&&r<=qr){
		if(t){
			tree[node].mn=min(tree[node].mn,x);
			tree[node].mx=min(tree[node].mx,x);
		}
		else{
			tree[node].mn=max(tree[node].mn,x);
			tree[node].mx=max(tree[node].mx,x);
		}
		return;
	}
	tree[node].mn=INF;
	tree[node].mx=-INF;
	int mid=(l+r)/2;
	update(node<<1,l,mid,ql,qr,x,t);
	update(node<<1|1,mid+1,r,ql,qr,x,t);
}
void query(int node,int l,int r,int finalHeight[]){
	if(l==r){
		finalHeight[l-1]=tree[node].mn;
		return;
	}
	push(node,l,r);
	int mid=(l+r)/2;
	query(node<<1,l,mid,finalHeight);
	query(node<<1|1,mid+1,r,finalHeight);
}
void buildWall(int n, int k, int op[], int left[], 
	int right[], int height[], int finalHeight[]){
	// build(1,0,n-1);
	for(int i=0;i<k;i++){
		update(1,1,n,left[i]+1,right[i]+1,height[i],op[i]-1);
	}
	// for(int i=0;i<n;i++){
		// int x=query(1,1,n,i);
		// cout<<x<<" ";
		// finalHeight[i]=x;
	// }
	// cout<<endl;
	query(1,1,n,finalHeight);
	for(int i=0;i<n;i++){
		// cout<<finalHeight[i]<<" ";
	}
	// cout<<endl;
	return;
}

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