Submission #204485

#	Time	Username	Problem	Language	Result	Execution time	Memory
204485		T0p_	Just Long Neckties (JOI20_ho_t1)	C++14	100 / 100	253 ms	18524 KiB

ho_t1

#include<bits/stdc++.h>
using namespace std;

#define pb push_back

struct data
{
	long long val;
	long long pos;	
	bool operator < (const data & o) const
	{
		return val < o.val;	
	}
};

long long b[200200], ans[200200], seg[2][800800];
data a[200200];
vector<data> v;

void build(int l, int r, int idx)
{
	if(l == r)
	{
		seg[0][idx] = max(0ll, a[l].val - b[l]);
		seg[1][idx] = max(0ll, a[l+1].val - b[l]);
		return ;
	}
	int mid = (l+r)>>1;
	build(l, mid, idx<<1);
	build(mid+1, r, idx<<1|1);
	for(int i=0 ; i<2 ; i++)
		seg[i][idx] = max(seg[i][idx<<1], seg[i][idx<<1|1]);
}

long long query(int l, int r, int idx, int a, int b, int s)
{
	if(r < a || b < l) return -1e15;
	if(a <= l && r <= b) return seg[s][idx];
	int mid = (l+r)>>1;
	return max(query(l, mid, idx<<1, a, b, s), query(mid+1, r, idx<<1|1, a, b, s));
}

int main()
{
	int n;
	scanf(" %d",&n);
	for(int i=1 ; i<=n+1 ; i++)
	{
		long long d;
		scanf(" %lld",&d);
		a[i] = {d, i};
	}
	for(int i=1 ; i<=n ; i++)
		scanf(" %lld",&b[i]);
	sort(a+1, a+n+2);
	sort(b+1, b+n+1);
	build(1, n, 1);
	for(int i=1 ; i<=n+1 ; i++)
	{
		long long d = max(query(1, n, 1, 1, i-1, 0), query(1, n, 1, i, n, 1));
		v.pb({a[i].pos, d});
	}
	sort(v.begin(), v.end());
	for(int i=0 ; i<=n ; i++)
		printf("%lld ",v[i].pos);
	return 0;
}

Compilation message (stderr)

ho_t1.cpp: In function 'int main()':
ho_t1.cpp:46:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %d",&n);
  ~~~~~^~~~~~~~~~
ho_t1.cpp:50:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %lld",&d);
   ~~~~~^~~~~~~~~~~~
ho_t1.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %lld",&b[i]);
   ~~~~~^~~~~~~~~~~~~~~

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