oj.uz

Submission #162651

# Submission time Handle Problem Language Result Execution time Memory
162651 2019-11-09T07:16:18 Z nafis_shifat Wall (IOI14_wall) C++14
100 / 100
 929 ms 65588 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=2e6+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 376 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

Subtask #2
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 175 ms 8544 KB Output is correct
3 Correct 205 ms 4860 KB Output is correct
4 Correct 615 ms 12188 KB Output is correct
5 Correct 358 ms 12664 KB Output is correct
6 Correct 348 ms 12764 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 9 ms 1016 KB Output is correct
5 Correct 8 ms 888 KB Output is correct
6 Correct 8 ms 988 KB Output is correct
7 Correct 2 ms 256 KB Output is correct
8 Correct 177 ms 8244 KB Output is correct
9 Correct 206 ms 4984 KB Output is correct
10 Correct 602 ms 12324 KB Output is correct
11 Correct 357 ms 12792 KB Output is correct
12 Correct 349 ms 12812 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 178 ms 8696 KB Output is correct
15 Correct 35 ms 1912 KB Output is correct
16 Correct 633 ms 12636 KB Output is correct
17 Correct 357 ms 12480 KB Output is correct
18 Correct 359 ms 12536 KB Output is correct

Subtask #4
39.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 9 ms 1016 KB Output is correct
6 Correct 8 ms 1016 KB Output is correct
7 Correct 12 ms 376 KB Output is correct
8 Correct 277 ms 8824 KB Output is correct
9 Correct 207 ms 4984 KB Output is correct
10 Correct 614 ms 12384 KB Output is correct
11 Correct 351 ms 12792 KB Output is correct
12 Correct 352 ms 12792 KB Output is correct
13 Correct 2 ms 376 KB Output is correct
14 Correct 179 ms 8692 KB Output is correct
15 Correct 36 ms 1784 KB Output is correct
16 Correct 648 ms 12540 KB Output is correct
17 Correct 376 ms 12536 KB Output is correct
18 Correct 369 ms 12644 KB Output is correct
19 Correct 925 ms 63864 KB Output is correct
20 Correct 886 ms 61424 KB Output is correct
21 Correct 912 ms 64040 KB Output is correct
22 Correct 895 ms 61444 KB Output is correct
23 Correct 918 ms 61388 KB Output is correct
24 Correct 914 ms 61560 KB Output is correct
25 Correct 899 ms 61432 KB Output is correct
26 Correct 929 ms 63868 KB Output is correct
27 Correct 913 ms 65588 KB Output is correct
28 Correct 903 ms 62360 KB Output is correct
29 Correct 897 ms 62388 KB Output is correct
30 Correct 882 ms 62456 KB Output is correct