oj.uz

Submission #162644

# Submission time Handle Problem Language Result Execution time Memory
162644 2019-11-09T07:09:39 Z nafis_shifat Wall (IOI14_wall) C++14
61 / 100
 669 ms 17024 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=1e5+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 960 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 376 KB Output is correct
2 Correct 173 ms 8540 KB Output is correct
3 Correct 208 ms 4864 KB Output is correct
4 Correct 583 ms 12280 KB Output is correct
5 Correct 352 ms 12828 KB Output is correct
6 Correct 345 ms 12756 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 504 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 11 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 178 ms 8624 KB Output is correct
9 Correct 207 ms 4984 KB Output is correct
10 Correct 601 ms 12244 KB Output is correct
11 Correct 360 ms 12716 KB Output is correct
12 Correct 347 ms 12892 KB Output is correct
13 Correct 2 ms 256 KB Output is correct
14 Correct 180 ms 8736 KB Output is correct
15 Correct 36 ms 2268 KB Output is correct
16 Correct 667 ms 12588 KB Output is correct
17 Correct 362 ms 12664 KB Output is correct
18 Correct 358 ms 12536 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 4 ms 376 KB Output is correct
4 Correct 7 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 177 ms 8796 KB Output is correct
9 Correct 206 ms 5112 KB Output is correct
10 Correct 589 ms 12360 KB Output is correct
11 Correct 353 ms 12856 KB Output is correct
12 Correct 348 ms 12864 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 180 ms 8892 KB Output is correct
15 Correct 36 ms 2296 KB Output is correct
16 Correct 669 ms 12572 KB Output is correct
17 Correct 362 ms 12536 KB Output is correct
18 Correct 361 ms 12524 KB Output is correct
19 Runtime error 284 ms 17024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Halted 0 ms 0 KB -