Submission #12260

#	Time	Username	Problem	Language	Result	Execution time	Memory
12260		progressive	수족관 3 (KOI13_aqua3)	C++98	18 / 100	92 ms	11632 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;
}node[MAXN];
void setlr(Node *n,long long int l,long long int r)
{
	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);
	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++)
	{
		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 maxv=0LL;
	for(int i=0;i<n;i++)
		if(maxv<node[i].val)
			maxv=node[i].val;
	printf("%lld",maxv);
	return 0;
}

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