Submission #770116

#	Time	Username	Problem	Language	Result	Execution time	Memory
770116		YassirSalama	벽 (IOI14_wall)	C++14	0 / 100	1 ms	212 KiB

wall

#include "wall.h"
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e6;
int tree[4*MAXN];
int lazy[4*MAXN];
const int INF=2e9;
void push_max(int node,int l,int r){
	if(lazy[node]){
		tree[node]=max(tree[node],lazy[node]);
		if(l!=r) lazy[node<<1]=lazy[node],
				 lazy[node<<1|1]=lazy[node];
		lazy[node]=0;
	}
}
void update_max(int node,int l,int r,int ql,int qr,int x){
	push_max(node,l,r);
	if(ql<=l&&r<=qr) {
		lazy[node]=x;
		push_max(node,l,r);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid) update_max(node<<1,l,mid,ql,qr,x);
	if(qr>mid) update_max(node<<1|1,mid+1,r,ql,qr,x);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
void build1(int node,int l,int r){
	push_max(node,l,r);
	if(l==r) {lazy[node]=INF;return;}
	int mid=(l+r)/2;
	build1(node<<1,l,mid);
	build1(node<<1|1,mid+1,r);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
	lazy[node]=INF;
}
void push_min(int node,int l,int r){
	if(lazy[node]!=INF){
		tree[node]=min(tree[node],lazy[node]);
		if(l!=r) lazy[node<<1]=lazy[node],
				 lazy[node<<1|1]=lazy[node];
		lazy[node]=INF;
	}
}
void update_min(int node,int l,int r,int ql,int qr,int x){
	push_min(node,l,r);
	if(ql<=l&&r<=qr) {
		lazy[node]=x;
		push_min(node,l,r);
		return;
	}
	int mid=(l+r)/2;
	if(ql<=mid) update_min(node<<1,l,mid,ql,qr,x);
	if(qr>mid) update_min(node<<1|1,mid+1,r,ql,qr,x);
	tree[node]=max(tree[node<<1],tree[node<<1|1]);
}
int query(int node,int l,int r,int ind){
	push_min(node,l,r);
	if(l==r) return tree[node];
	int mid=(l+r)/2;
	if(ind<=mid) return query(node<<1,l,mid,ind);
	return query(node<<1|1,mid+1,r,ind);
}
void buildWall(int n, int k, int op[], int left[], int right[], 
	int height[], int finalHeight[]){
	int nxtindex=0;
	for(int i=0;i<k;i++){
		if(op[i]==2) {
			nxtindex=i;
			break;
		}
	}
	for(int i=0;i<nxtindex;i++){
		int l=left[i];
		int r=right[i];
		int x=height[i];
		update_max(1,0,n-1,l,r,x);
	}
	build1(1,0,n-1);
	for(int i=nxtindex;i<k;i++){
		int l=left[i];
		int r=right[i];
		int x=height[i];
		update_min(1,0,n-1,l,r,x);
	}
	for(int i=0;i<n;i++){
		finalHeight[i]=query(1,0,n-1,i);
	}
	return;
}

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