Submission #1160811

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160811		hackstar	벽 (IOI14_wall)	C++17	100 / 100	497 ms	151592 KiB

wall

#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx,avx2")
#include<bits/stdc++.h>
using namespace std;
struct Node{
	int mn,mx,val;
	bool uniform;
};
vector<Node> seg;
int N;
void build(int idx,int l,int r){
	if(l==r){seg[idx]={0,0,0,true};return;}
	int mid=(l+r)/2;
	build(idx*2,l,mid);
	build(idx*2+1,mid+1,r);
	seg[idx]={0,0,0,true};
}
void pushDown(int idx,int l,int r){
	if(!seg[idx].uniform||l==r)return;
	int mid=(l+r)/2;
	seg[idx*2]={seg[idx].val,seg[idx].val,seg[idx].val,true};
	seg[idx*2+1]={seg[idx].val,seg[idx].val,seg[idx].val,true};
	seg[idx].uniform=false;
}
void update(int idx,int l,int r,int ql,int qr,int op,int h){
	if(ql>r||qr<l)return;
	if(ql<=l&&r<=qr){
		if(op==1){
			if(seg[idx].mn>=h)return;
			if(seg[idx].mx<h){seg[idx]={h,h,h,true};return;}
		}else{
			if(seg[idx].mx<=h)return;
			if(seg[idx].mn>h){seg[idx]={h,h,h,true};return;}
		}
	}
	pushDown(idx,l,r);
	int mid=(l+r)/2;
	update(idx*2,l,mid,ql,qr,op,h);
	update(idx*2+1,mid+1,r,ql,qr,op,h);
	seg[idx].mn=min(seg[idx*2].mn,seg[idx*2+1].mn);
	seg[idx].mx=max(seg[idx*2].mx,seg[idx*2+1].mx);
	if(seg[idx*2].uniform&&seg[idx*2+1].uniform&&seg[idx*2].val==seg[idx*2+1].val)
		seg[idx]={seg[idx*2].val,seg[idx*2].val,seg[idx*2].val,true};
	else seg[idx].uniform=false;
}
void query(int idx,int l,int r,vector<int>& ans){
	if(l==r){ans[l]=seg[idx].uniform?seg[idx].val:seg[idx].mn;return;}
	pushDown(idx,l,r);
	int mid=(l+r)/2;
	query(idx*2,l,mid,ans);
	query(idx*2+1,mid+1,r,ans);
}
void buildWall(int n,int k,int op[],int left[],int right[],int height[],int finalHeight[]){
	N=n;
	seg.assign(4*n,{0,0,0,true});
	build(1,0,n-1);
	for(int i=0;i<k;i++){
		update(1,0,n-1,left[i],right[i],op[i],height[i]);
	}
	vector<int> ans(n,0);
	query(1,0,n-1,ans);
	for(int i=0;i<n;i++)finalHeight[i]=ans[i];
}

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