Submission #1031057

#	Time	Username	Problem	Language	Result	Execution time	Memory
1031057		tolbi	Wall (IOI14_wall)	C++17	0 / 100	276 ms	11528 KiB

wall

#include "wall.h"
#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 1e9+7;
#define tol(bi) (1LL<<((int)(bi)))
void _upd(array<int,4> &old, array<int,3> upd){
	if (upd[1]==1){
		if (old[0]<=upd[0]){
			old[0]=min(old[2],max(old[0],upd[0]));
			old[1]=upd[2];
		}
	}
	else {
		if (old[2]>=upd[0]){
			old[2]=max(old[0],min(old[2],upd[0]));
			old[3]=upd[2];
		}
	}
}
constexpr int MAXN = 2000000;
array<int,2> segtree[MAXN*4];
array<int,2> lazy[MAXN*4];
void upd(array<int,2> &old, array<int,2> &u){
	if (u[0]==-1){
		old[1]=min(old[1],u[1]);
		old[0]=min(old[0],old[1]);
	}
	else {
		old[0]=max(old[0],u[0]);
		old[1]=max(old[1],old[0]);
	}
}
struct SegTree{
	int sz;
	SegTree(int n){
		sz=tol(ceil(log2(n)+1))-1;
		fill(segtree,segtree+sz,array<int,2>{-1,MOD});
		fill(lazy,lazy+sz,array<int,2>{-1,MOD});
	}
	void dallan(int node){
		upd(segtree[node],lazy[node]);
		if (node*2+1<sz){
			if (lazy[node*2+1]!=array<int,2>{-1,MOD} && (lazy[node][0]==-1)!=(lazy[node*2+1][0]==-1)) dallan(node*2+1);
			upd(lazy[node*2+1],lazy[node]);
			if (lazy[node*2+2]!=array<int,2>{-1,MOD} && (lazy[node][0]==-1)!=(lazy[node*2+1][0]==-1)) dallan(node*2+2);
			upd(lazy[node*2+2],lazy[node]);
		}
		lazy[node]={-1,MOD};
	}
	void update(int tl, int tr, array<int,2> val, int l = 0, int r = -1, int node = 0){
		if (r==-1) r = sz/2;
		dallan(node);
		if (l>=tl && r<=tr){
			return lazy[node]=val, dallan(node);
		}
		if (l>tr || r<tl) return;
		int mid = l+(r-l)/2;
		if (tl<=mid) update(tl, tr, val, l, mid, node*2+1);
		if (mid<tr) update(tl, tr, val, mid+1, r, node*2+2);
	}
	int query(int x){
		int l = 0, r = sz/2;
		int node = 0;
		dallan(node);
		while (l<r){
			int mid = l+(r-l)/2;
			if (mid>=x){
				r=mid,node=node*2+1;
			}
			else {
				l=mid+1,node=node*2+2;
			}
			dallan(node);
		}
		return segtree[node][0];
	}
};

void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[]){
	SegTree segtree(n);
	for (int i = 0; i < k; i++){
		if (op[i]==1){
			segtree.update(left[i],right[i],{height[i],MOD});
		}
		else {
			segtree.update(left[i],right[i],{-1,height[i]});
		}
	}
	for (int i = 0; i < n; ++i)
	{
		finalHeight[i]=max(0,segtree.query(i));
	}
}

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