Submission #202276

#	Time	Username	Problem	Language	Result	Execution time	Memory
202276		nafis_shifat	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	377 ms	7544 KiB

ho_t1

#include<bits/stdc++.h>
#define pii pair<int,int>
#define ll long long
#define f first
#define s second
 
using namespace std;
const int mxn=2e5+6;
int tree[4*mxn]={};

int query(int node,int b,int e,int p,int v=0)
{

	if(b==e)return max(v,tree[node]);
	int mid=b+e>>1;

	if(p<=mid)return query(node<<1,b,mid,p,max(v,tree[node]));
	else return query(node*2+1,mid+1,e,p,max(v,tree[node]));
    
}
void update(int node, int b,int e,int l,int r,int v)
{
	if(b>r || e<l)return;
	if(b>=l && e<=r)
	{
		tree[node]=max(tree[node],v);
		return;
	}    
	int mid=b+e>>1;
	int left=node<<1;
	int right=left|1;
	update(left,b,mid,l,r,v);
	update(right,mid+1,e,l,r,v);
}
int main()
{
	
 	int n;
 	cin>>n;
 	pii a[mxn];
 	int b[mxn];
 	for(int i=1;i<=n+1;i++)
 	{
 		cin>>a[i].f;
 		a[i].s=i;
 	}

 	sort(a+1,a+n+2);

 	for(int i=1;i<=n;i++)cin>>b[i];
    sort(b+1,b+n+1);
 	for(int i=1;i<=n;i++)
 	{
 		int d1=max(a[i].f-b[i],0);
 		int d2=max(a[i+1].f-b[i],0);

 		update(1,1,n+1,1,i,d2);
 		update(1,1,n+1,i+1,n+1,d1);
 		
 
 	}
 
 	int res[mxn];
 	for(int i=1;i<=n+1;i++)
 	{
 		res[a[i].s]=query(1,1,n+1,i);
 	
 	}
 	for(int i=1;i<=n+1;i++)cout<<res[i]<<" ";
 	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 1 / 1
• Subtask 2: 8 / 8
• Subtask 3: 91 / 91