Submission #72260

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

box

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

Compilation message (stderr)

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

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