oj.uz

Submission #162646

# Submission time Handle Problem Language Result Execution time Memory
162646 2019-11-09T07:11:31 Z nafis_shifat Wall (IOI14_wall) C++14
61 / 100
 683 ms 16872 KB 
#include "wall.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
using namespace std;
const int mx=2e5+10;
const int inf=1e9+10;
pii tree[4*mx];
int curval[4*mx];
void merge(int par,int kid)
{
	if(curval[par]!=-1)
	{
		curval[kid]=curval[par];
		tree[kid]={inf,-1};
		return;
	}

	if(curval[kid]!=-1)
	{
		if(curval[kid]<tree[par].s)
		{
			curval[kid]=tree[par].s;
		}
		else if(curval[kid]>tree[par].f)
		{
			curval[kid]=tree[par].f;
		}
		return;
	}
	tree[kid].f=min(tree[kid].f,tree[par].f);
	tree[kid].s=max(tree[kid].s,tree[par].s);
	
	if(tree[kid].f<=tree[kid].s)
	{
		if(tree[kid].f==tree[par].f)
		{
			curval[kid]=tree[kid].f;
		}
		else
		{
			curval[kid]=tree[kid].s;
		}
		tree[kid]={inf,-1};
		return;
	}
	curval[kid]=-1;

}
int query(int node,int b,int e,int p)
{
	if(curval[node]!=-1)
	{
	    return curval[node];
	}
	if(b==e)
	{
	    
		if(tree[node].s!=-1)return tree[node].s;
		return 0;
	}
	
	int mid=b+e>>1;
	int left=node<<1;
	int right=left|1;

	if(tree[node].f!=inf || tree[node].s!=-1)
	{
		merge(node,left);
		merge(node,right);
	}

	if(p<=mid)return query(left,b,mid,p);
	return query(right,mid+1,e,p);
}


void update(int node, int b,int e,int l,int r,int val,int type)
{
	if(b>r||e<l)return;


	if(b>=l && e<=r)
	{
		if(type==1)
		{
			if(curval[node]!=-1)
			{
				curval[node]=max(curval[node],val);
				return;
			}
			if(val>tree[node].f)
			{
				curval[node]=val;
				tree[node]={inf,-1};
				return;
			}
			tree[node].s=max(tree[node].s,val);
			curval[node]=-1;
		}		
		else
		{
			if(curval[node]!=-1)
			{
				curval[node]=min(curval[node],val);
				return;
			}
			if(val<tree[node].s)
			{
				curval[node]=val;
				tree[node]={inf,-1};
				return;
			}
			tree[node].f=min(tree[node].f,val);
			curval[node]=-1;
		}
		return;
	}
	
	int mid=b+e>>1;    
	int left=node<<1;
	int right=left|1;
	
	merge(node,left);
	merge(node,right);
	
	tree[node]={inf,-1};
	curval[node]=-1;

	
	update(left,b,mid,l,r,val,type);
	update(right,mid+1,e,l,r,val,type);


}





void buildWall(int n, int k, int op[], int left[], int right[], int height[], int finalHeight[])
{
	for(int i=0;i<k;i++)
	{
		int l=left[i]+1;
		int r=right[i]+1;
		int v=height[i];
		update(1,1,n,l,r,v,op[i]);
	}
	for(int i=0;i<n;i++)finalHeight[i]=query(1,1,n,i+1);
  return;
}

Compilation message

wall.cpp: In function 'int query(int, int, int, int)':
wall.cpp:65:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;
          ~^~
wall.cpp: In function 'void update(int, int, int, int, int, int, int)':
wall.cpp:122:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int mid=b+e>>1;    
          ~^~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 9 ms 1016 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 8 ms 1016 KB Output is correct

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 175 ms 8440 KB Output is correct
3 Correct 203 ms 4836 KB Output is correct
4 Correct 599 ms 12188 KB Output is correct
5 Correct 357 ms 12792 KB Output is correct
6 Correct 349 ms 12664 KB Output is correct

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 9 ms 1016 KB Output is correct
5 Correct 8 ms 892 KB Output is correct
6 Correct 8 ms 1016 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 278 ms 8284 KB Output is correct
9 Correct 206 ms 4800 KB Output is correct
10 Correct 596 ms 12160 KB Output is correct
11 Correct 356 ms 12592 KB Output is correct
12 Correct 346 ms 12748 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 178 ms 8424 KB Output is correct
15 Correct 35 ms 1912 KB Output is correct
16 Correct 683 ms 12328 KB Output is correct
17 Correct 389 ms 12308 KB Output is correct
18 Correct 360 ms 12408 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 504 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 8 ms 1016 KB Output is correct
5 Correct 8 ms 1016 KB Output is correct
6 Correct 8 ms 1016 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 176 ms 8440 KB Output is correct
9 Correct 206 ms 4680 KB Output is correct
10 Correct 659 ms 12084 KB Output is correct
11 Correct 361 ms 12580 KB Output is correct
12 Correct 360 ms 12636 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 178 ms 8400 KB Output is correct
15 Correct 36 ms 1784 KB Output is correct
16 Correct 657 ms 12536 KB Output is correct
17 Correct 358 ms 12372 KB Output is correct
18 Correct 357 ms 12448 KB Output is correct
19 Runtime error 205 ms 16872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -