oj.uz

Submission #12259

# Submission time Handle Problem Language Result Execution time Memory
12259 2014-12-26T05:04:29 Z progressive 수족관 3 (KOI13_aqua3) C++
18 / 100
 88 ms 11632 KB 
#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.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 11632 KB Output is correct
2 Correct 0 ms 11632 KB Output is correct
3 Correct 0 ms 11632 KB Output is correct
4 Correct 0 ms 11632 KB Output is correct
5 Correct 0 ms 11632 KB Output is correct
6 Correct 0 ms 11632 KB Output is correct
7 Correct 0 ms 11632 KB Output is correct
8 Correct 0 ms 11632 KB Output is correct
9 Correct 0 ms 11632 KB Output is correct
10 Correct 0 ms 11632 KB Output is correct

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 11632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 21.0

# Verdict Execution time Memory Grader output
1 Incorrect 84 ms 11632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 11632 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 80 ms 11632 KB Output isn't correct
2 Halted 0 ms 0 KB -