Submission #72267

#	Time	Username	Problem	Language	Result	Execution time	Memory
72267		https://blog.naver.com/nywoo19 (#118)	Box Run (FXCUP3_box)	C++17	100 / 100	738 ms	26756 KiB

box

#include<cstdio>
#include<vector>
#include<algorithm>
#define ll long long
using namespace std;
ll seg[2000000];
ll a[500100], ch[500100], dap[500100];
vector<ll> vt;
ll getidx(ll x) {
	return lower_bound(vt.begin(), vt.end(), x) - vt.begin();
}
ll update(ll pos, ll val, ll node, ll x, ll y)
{
	if (pos < x || pos > y)return seg[node];
	if (x == y)return seg[node] = val;
	ll mid = (x + y) / 2;
	return seg[node] = max(update(pos, val, node * 2, x, mid), update(pos, val, node * 2 + 1, mid + 1, y));
}
ll query(ll lo, ll hi, ll node, ll x, ll y)
{
	if (hi < x || y < lo)return 0;
	if (lo <= x&&y <= hi)return seg[node];
	ll mid = (x + y) / 2;
	return max(query(lo, hi, node * 2, x, mid), query(lo, hi, node * 2 + 1, mid + 1, y));
}
int main()
{
	ll n;
	scanf("%lld", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%lld", &a[i]);
		vt.push_back(a[i]);
	}
	sort(vt.begin(), vt.end());
	vt.erase(unique(vt.begin(), vt.end()), vt.end());
	for (int i = 1; i <= n; i++)
		a[i] = getidx(a[i]);
	int t = vt.size();
	for (int i = 1; i <= n; i++)
	{
		ch[i] = query(a[i], n - 1, 1, 0, t - 1);
		update(a[i], i, 1, 0, t - 1);
	}
	int prev = 0;
	for (int i = 2; i <= n; i++)
	{
		if (i - ch[i] - 1 > prev)
		{
			for (int y = prev + 1; y <= i - ch[i] - 1; y++)
				dap[y] = i - y;
			prev = i - ch[i] - 1;
		}
	}
	for (int i = 1; i <= n; i++) {
		if (dap[i])
			printf("%lld ", dap[i]);
		else
			printf("-1 ");
	}
}

Compilation message (stderr)

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

• Subtask 1: 17 / 17
• Subtask 2: 83 / 83