Submission #12261

#	Time	Username	Problem	Language	Result	Execution time	Memory
12261		progressive	수족관 3 (KOI13_aqua3)	C++98	18 / 100	88 ms	12804 KiB

aqua3

#include<cstdio>
#define MAXN 150005
long long int cut[MAXN];
long long int height[MAXN];
struct Node
{
	Node *parent;
	Node *lchild;
	Node *rchild;
	long long int val;
	long long int lazym;
	int no;
	Node *maxnode;
	long long int maxv;
}node[MAXN];
inline void lazyupdate(Node *n)
{
	if(n->lazym)
	{
		n->val-=n->lazym;
		n->maxv-=n->lazym;
		if(n->rchild) n->rchild->lazym+=n->lazym;
		if(n->lchild) n->lchild->lazym+=n->lazym;
		n->lazym=0;
	}
}
void cutn(Node *n)
{
	if(n->parent)
	{
		n->lazym+=n->val-n->parent->val;
		cutn(n->parent);
	}
	else
	{
		n->lazym+=n->val;
	}
	lazyupdate(n);
	return;
}
void upd(Node *n)
{
	while(n)
	{
		n->maxnode=n;
		n->maxv=n->val;
		if(n->lchild)
		{
			lazyupdate(n->lchild);
			if( (n->maxv) < (n->lchild->maxv) )
			{
				n->maxv=(n->lchild->maxv);
				n->maxnode=n->lchild->maxnode;
			}
		}
		if(n->rchild)
		{
			lazyupdate(n->rchild);
			if( (n->maxv) < (n->rchild->maxv) )
			{
				n->maxv=(n->rchild->maxv);
				n->maxnode=n->rchild->maxnode;
			}
		}
		n=n->parent;
	}
}
void setlr(Node *n,long long int l,long long int r)
{
	n->lazym=0;
	if(n->parent)
		n->val=(n->parent->val)+(height[n->no]-height[n->parent->no])*(r-l);
	else
		n->val=height[n->no]*(r-l);
	if(n->lchild)
		setlr(n->lchild,l,cut[n->no]);
	if(n->rchild)
		setlr(n->rchild,cut[(n->no)+1],r);
	n->maxnode=n;
	n->maxv=n->val;
	if(n->lchild)
		if( (n->maxv) < (n->lchild->maxv) )
		{
			n->maxv=(n->lchild->maxv);
			n->maxnode=n->lchild->maxnode;
		}
	if(n->rchild)
		if( (n->maxv) < (n->rchild->maxv) )
		{
			n->maxv=(n->rchild->maxv);
			n->maxnode=n->rchild->maxnode;
		}
	return;
}
int main()
{
	int n,k;
	scanf("%d",&n);
	n=n/2-1;
	scanf("%*lld%*lld");
	for(int i=0;i<n;i++)
	{
		scanf("%*lld%*lld");
		scanf("%lld%lld",&cut[i+1],&height[i]);
	}
	scanf("%*lld%*lld");
	scanf("%d",&k);
	node[0].parent=node[0].lchild=node[0].rchild=NULL;
	node[0].no=0;
	for(int i=1;i<n;i++)
	{
		//connexion of node[i-1] and node[i]
		Node *con=&node[i-1];
		node[i].parent=node[i].lchild=node[i].rchild=NULL;
		node[i].no=i;
		while(true)
		{
			if( height[con->no] < height[i] )
			{
				if(con->rchild)
				{
					node[i].lchild=con->rchild;
					con->rchild->parent=&node[i];
				}
				con->rchild=&node[i];
				node[i].parent=con;
				break;
			}
			else
			{
				if(con->parent)
					con=con->parent;
				else
				{
					con->parent=&node[i];
					node[i].lchild=con;
					break;
				}
			}
		}
	}
	Node *root;
	for(int i=0;i<n;i++)
		if(!node[i].parent)
		{
			root=&node[i];
			break;
		}
	setlr(root,cut[0],cut[n]);
	long long int ans=0;
	for(int i=0;i<k;i++)
	{
		ans+=root->maxv;
		cutn(root->maxnode);
		upd(root->maxnode);
	}
	printf("%lld",ans);
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 30
• Subtask 3: 0 / 21
• Subtask 4: 0 / 15
• Subtask 5: 0 / 16